26 Jun 2010, 09:25
Cimg0269_pragsmall

Seth Arnold (22 posts)

I’m having trouble coming up with a happy Prolog Fibonacci function.

The function I’d like to have would work with the full unification:

fib(3,5,X) --> X = 8 ?
fib(3,X,8) --> X = 5 ?
fib(X,5,8) --> X = 3 ?

It’d be cool if it could also handle:

fib(X,Y,89) --> X = 34, Y = 55 ?

But the best I have been able to do so far is only the very first style:

fib(3,5,X) --> X = 8 ?

Is my goal realistic? If so, how would it best be solved?

When searching for other examples of Fibonacci series in Prolog, I’ve only found other programs with similar limitations.

Here’s what I’ve got so far:

fib(0, 1, 1).
fib(1, 1, 2).
fib(N, M, F) :-
        F is N+M,
        M1 is N,
        N1 is M-N,
        fib(N1, M1, F1),
        F1 is N1+M1.

Thanks

27 Oct 2012, 18:55
Generic-user-small

Bernard Kaiflin (8 posts)

I did some Turbo Prolog (MS-DOS) in 1987, forgot almost all, re-discovered it with the book. So I am again a newbie. My solution uses the dynamic database capability, (see GNU-Prolog doc 7.7 Dynamic clause management, page 60 of gprolog.pdf), which allows to add facts into memory with asserta/z.

The code :

fibonacci(Max, Result) :-
    M = 1,
    N = 1,
    fib1(Max, M, N, [2, 1, 1], R),
    reverse(R, Result).
fib1(Max, M, N, Inter, Result) :-
    NewM is N,
    NewN is M + N,
    /* as long as next N <= Max, recurse with next pair : */
    NewN =< Max -> ( /* if true */
        assertz(fibo(M, N, NewN)), /* this adds a new fact */
        write('added fibo('), write(M), write(', '),
        write(N), write(', '), write(NewN), write(')\n'),
        /* compose the intermediate list with [M|Inter] and recurse : */
        fib1(Max, NewM, NewN, [NewN|Inter], Result)
                   );
    /* else return the intermediate list : */
    Result = Inter.

The execution with GNU-Prolog 1.3.1 :

| ?- fibonacci(89, R). added fibo(1, 1, 2) added fibo(1, 2, 3) added fibo(2, 3, 5) added fibo(3, 5, 8) added fibo(5, 8, 13) added fibo(8, 13, 21) added fibo(13, 21, 34) added fibo(21, 34, 55) added fibo(34, 55, 89)

R = [1,1,2,2,3,5,8,13,21,34,55,89]

(40 ms) yes | ?- fibo(X, Y, 89).

X = 34 Y = 55

yes | ?- fibo(3, 5, 8).

true ?

(10 ms) yes | ?- fibo(3, X, 8).

X = 5 ?

(10 ms) yes | ?- fibo(X, 5, 8).

X = 3 ?

yes | ?- fibo(3, 5, X).

X = 8 ?

yes

HTH Bernard

  You must be logged in to comment