fibonacci in prolog

[ronnieaka]

i have been trying in vain to implement fibonacci in prolog, and so far i've done that in c++,javascript,python and java. but it just irritates me since i'm new to prolog and i just can't code much, because i haven't seen the prolog equivalents of c++'s for loops,if-else statements,basic variable usage etc.. but still i learnt whatever i could from 4-5 books i downloaded off the net, a few university lecture notes,etc.

here's my code to print N elements of the fibonacci series ( here N means excluding the first two basic elements of the series, 0,1.

start:-

	write('Enter n '),nl,
        read(N),
	write('0 1'), %printing first two necessary numbers of the series
	fib(N,0,1).

% so i'm reading N, the no of elements of the fibonacci series the user would like to %print, 

fib(N,A,B):- % A and B are the n-2 and n-1 that add up to give n, 
	N>1,
	C = A+B,
	B = C,
	A = B,
	write(C),nl,
	X is N-1,
	fib(X,A,B).  % i directly put N-1 as the first argument in previous versions..would that create problems?

also i tried to do it this way too:

fib(0, 0, A):-!.
fib(1, 1, A):-!.

fib(N, X, A):-
	N1 is N-1,
	N2 is N-2,

	fib(N1, X1,1),
        fib(N2, X2,0),

        X is X1+X2.

display(X,A).

display(X,A):-
	A==1,
	write(X),nl.

the A argument in display is a flag. it means, whenever the brancing happens from N-1 side of the recursion, the sum will be printed then only.. otherwise it will print like this: 1 2 1 3 1 5 etc

[TrustyTony]

From http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/Prolog%20examples.pdf, we find simple recursive fibonacci and also an efficient one:

fib(0, 0).
fib(X, Y):- X > 0, fib(X, Y, _).

fib(1, 1, 0).
fib(X, Y1, Y2) :- X > 1,
             X1 is X - 1,
             fib(X1, Y2, Y3),
             Y1 is Y2 + Y3.

[ronnieaka]

well i could print the nth term, that was done by the second method i wrote, obviously without that 'display' predicate ,which i added to print all the terms upto nth element - which is what i want to do here. print all the fibonacci numbers upto the nth term

please see if there's something really terribly wrong logically in my first implementation, because that's the simplest way i did it myself. And i don't like to copy, because i don't like to understand others' logic, that would hinder my process of making my own logic. Anyways thanks for the reply which had some concern.

[TrustyTony]

I must say that I do not understand it, I understand the solution which posted, which is really simple.

From my logic (I do not know the environment you are using and I can not get your code to run in GNU Prolog):
From

N>1,
	C = A+B,
	B = C,
	A = B,

follows that C = C + B => B=0 => A=0 => C = A + B = 0, for all N > 1

[ronnieaka]

i hope you didn't miss this out:

fib(N,0,1).

[TrustyTony]

Even if not consider the conditions in the clause.

The basic requirement of one bigger fibonacci number (ok , there is 2 = 1 + 1, and 1 = 1 + 0) as it also have equal previous values A and B, means there should be three consecutive numbers equal in fibonacci sequence. And what if the user input N is not valid fibonacci number? And if it would be surely the previous numbers before that are not 0 and 1 as you assert.

fib(N,A,B):- % A and B are the n-2 and n-1 that add up to give n, 
	X is N-1,
	fib(X,A,B).

[ronnieaka]

From http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/Prolog%20examples.pdf, we find simple recursive fibonacci and also an efficient one:

fib(0, 0).
fib(X, Y):- X > 0, fib(X, Y, _).

fib(1, 1, 0).
fib(X, Y1, Y2) :- X > 1,
             X1 is X - 1,
             fib(X1, Y2, Y3),
             Y1 is Y2 + Y3.

well that worked, with a little modification to print all the numbers upto N

here's the modded code :

fib(0, 0).
fib(1,0):-write('0').
fib(X, Y):- X>1,write('0 1 '),X > 0, fib(X-1, Y, _).


fib(1, 1, 0).
fib(X, Y1, Y2) :- X > 1,
             X1 is X - 1,
             fib(X1, Y2, Y3),
             Y1 is Y2 + Y3,
	write(Y1),write(' ').

[ronnieaka]

please do reply. i will have to close the thread to any further comments

and most of all, thank you for taking notice and helping me out

[TrustyTony]

You can not close thread, you can only mark it solved, which you can later undo if something of same topic comes up. Usually it is preferable to make new thread, if necessary linking to an old one.

[ronnieaka]

okay, about your this particular point:
"And what if the user input N is not valid fibonacci number? And if it would be surely the previous numbers before that are not 0 and 1 as you assert."

In that,you are referring to the 1st version of my code.

now i don't know if i'm understanding you correct, but maybe this is what you didn't see.

i'm starting the program from the start/0.
then there it will simply ask you to enter N ( the no of fibonacci series numbers you want to print).

and surely you didn't miss this: fib(N,0,1) , thus, always, A=0, B=1, whatever N maybe (valid fibonacci number or not), and then in the recursive calls, A and B will change values as A=B, and B will be C which is A+B (before A and B change values, obviously).

[TrustyTony]

A or B never change value, they are what they are unified with in the rule. This is prolog, you can not say 1 unifies with 2 as it will never happen and Prolog system knows it.