CODEWITHSUNDEEP
prolograngefibonacci
Shrp91
Shrp91

Reputation: 163

Sequence of Fibonnaci Numbers - Prolog

While attempting to learn Prolog I came across a good exercise which was to write a program that displays the Nth Fibonacci number. After some work I got it working and then decided to see if I could write a program that displays a range of Fibonacci numbers according to the input.

For instance the input:

?- fib_sequence(2,5,Output).

Gives the output:

?- Output = [1,1,2,3]

I am having difficulty, however, in finding a good starting point. This is what I have so far:

fib(0, 0).
fib(1, 1).
fib(N, F) :- X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B.

fib_sequence(A,B,R) :- fib(A,Y) , fib(B,Z).

I know I must assign a value to R, but I'm not sure how to assign multiple values. Any help is greatly appreciated.

Upvotes: 3

Views: 3789

Answers (3)

lurker
lurker

Reputation: 58274

Here's yet another approach. First, I redid fib a little so that it only recursively calls itself once instead of twice. To do this, I created a predicate that returns the prior the last two Fibonacci values instead of the last one:

fib(N, F) :-
    fib(N, F, _).
fib(N, F, F1) :-
    N > 2,
    N1 is N-1,
    fib(N1, F1, F0),
    F is F0 + F1.
fib(1, 1, 0).
fib(2, 1, 1).

For getting the sequence, I chose an algorithm with the Fibonacci calculation built-in so that it doesn't need to call fib O(n^2) times. It does, however, need to reverse the list when complete:

fib_sequence(A, B, FS) :-
    fib_seq_(A, B, FSR),
    reverse(FSR, FS).

fib_sequence_(A, B, []) :-
    A > B.
fib_sequence_(A, B, [F]) :-
    A =:= B,
    fib(A, F, _).
fib_sequence_(A, B, [F1,F0]) :-
    1 is B - A,
    fib(B, F1, F0).
fib_sequence_(A, B, [F2,F1,F0|FT] ) :-
    B > A,
    B1 is B - 1,
    fib_sequence_(A, B1, [F1,F0|FT]),
    F2 is F1 + F0.

Here's one more way, to do it without the reverse, but the reverse method above still appears to be a little faster in execution.

fib_sequence_dl(A, B, F) :-
    fib_sequence_dl_(A, B, F, [_,_|[]]).

fib_sequence_dl_(A, B, [], _) :-
    A > B, !.
fib_sequence_dl_(A, B, [F], _) :-
    A =:= B,
    fib(A, F, _), !.
fib_sequence_dl_(A, B, [F0,F1|T], [F0,F1|T]) :-
    1 is B - A,
    fib(B, F1, F0), !.
fib_sequence_dl_(A, B, F, [F1,F2|T]) :-
    A < B,
    B1 is B - 1,
    fib_sequence_dl_(A, B1, F, [F0,F1|[F2|T]]),
    F2 is F0 + F1.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726779

Observe that your fib_sequence cannot be done in a single predicate clause: you need at least two to keep things recursive - one to produce an empty list when A is greater than B (i.e. we've exhausted the range from A to B), and another one to prepend X from fib(A,X) to a list that you are building, increment A by 1, and call fib_sequence recursively to produce the rest of the sequence.

The first predicate clause would look like this:

fib_sequence(A,B,[]) :- A > B.

The second predicate clause is a bit harder:

fib_sequence(A,B,[H|T]) :-
    A =< B                   /* Make sure A is less than or equal to B */
,   fib(A, H)                /* Produce the head value from fib(A,...) */
,   AA is A + 1              /* Produce A+1 */
,   fib_sequence(AA, B, T).  /* Produce the rest of the list */

Upvotes: 3

CapelliC
CapelliC

Reputation: 60034

Prolog has some helper builtin to handle numeric sequences, then as an alternative to dasblinkenlight' answer, here is an idiomatic 'query':

fib_sequence(First, Last, Seq) :-
    findall(F, (between(First,Last,N), fib(N,F)), Seq).

note that it will not work out-of-the-box with your fib/2, because there is a bug: I've added a condition that avoid the endless loop you would experience trying to backtrack on fib/2 solutions:

fib(N, F) :- N > 1, % added sanity check
    X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B.

Upvotes: 1

Related Questions