Efficient Fibonacci in Prolog

Question

I am trying to implement a Fibonacci predicate that can be efficiently used with CLP.

:- module(fibonacci, [fibonacci/2]).

fibonacci(N, F) :-
  ( var(N) ; integer(N) ),
  ( var(F) ; integer(F) ),
  ( var(F) ->
    ( integer(N) ->
      fib_1(N, F), !
    ; fib_3(0, N, F)
    )
  ; ( integer(N) ->
      fib_1(N, F0), F0 = F, !
    ; fib_2(0, F, N0), N0 = N, !
    )
  ).

fib_3(I, J, F) :-
  ( I = J, fib_1(I, F) ) ;
  ( I1 is I + 1, fib_3(I1, J, F) ).

fib_2(I, F, J) :-
  fib_1(I, F0),
  ( F = F0 -> 
    J = I, !
  ; ( F0 > F -> !, fail
    ; I1 is I + 1,
      fib_2(I1, F, J)
    )
  ).

fib_1(0, 0).
fib_1(1, 1).
fib_1(2, 1).
fib_1(N, F) :-
  var(F),
  N > 2,
  ( N mod 2 =:= 0 ->
    N0 is div(N, 2),
    N1 is N0 + 1,
    fib_1(N0, F0),
    fib_1(N1, F1),
    F is F0 * (2 * F1 - F0)
  ; N0 is div(N + 1, 2),
    N1 is N0 - 1,
    fib_1(N0, F0),
    fib_1(N1, F1),
    F is F0 * F0 + F1 * F1 
  ).

This is not the prettiest code, but it does what I want it to do.

?- fibonacci(A, 10).
false.

?- fibonacci(A, 13).
A = 7.

?- fibonacci(12, A).
A = 144.

?- fibonacci(12, 144).
true.

?- fibonacci(12, 145).
false.

?- fibonacci(A, B).
A = B, B = 0 ;
A = B, B = 1 ;
A = 2,
B = 1 ;
A = 3,
B = 2 ;
A = 4,
B = 3 ;
A = B, B = 5 .

What's the magic potion that is missing for this query to work:

fibonacci(_, B), B #< 1000

Is it rectifiable at all, or is CLP a completely different beast altogether, and every predicate that is CLP-compatible needs to understand more than just integers and vars?

gusbro gusbro · Accepted Answer · 2021-07-08T18:43:17

You should avoid using ! within an algorithm that uses clp(FD) as they don't mix well. Also if-then-else may backfire too. I'd also keep an eye on using var/1 within an algorithm that uses clp.

Here goes a solution that uses clp(FD) and accumulators to avoid double recursion:

fibonacci(0, 0).
fibonacci(1, 1).
fibonacci(N, F):-
  N #> 1,
  zcompare(C, 2, N),
  fibonacci(C, 2, N, 0, 1, F).
  
fibonacci(=, N, N, F1, F2, F):-
  F #= F1+F2.
fibonacci(<, N0, N, F1, F2, F):-
  N1 #= N0+1,
  F3 #= F1+F2,
  F #> F3,
  zcompare(C, N1, N),
  fibonacci(C, N1, N, F2, F3, F).

Also for the test you should issue the constraint over the expected number before calling fibonacci/2. So instead of fibonacci(_, B), B #< 1000. use B #< 1000, fibonacci(_, B).

sample runs:

?- fibonacci(10, F).
F = 55.

?- B #< 1000, fibonacci(_, B).
B = 0 ;
B = 1 ;
B = 1 ;
B = 2 ;
B = 3 ;
B = 5 ;
B = 8 ;
B = 13 ;
B = 21 ;
B = 34 ;
B = 55 ;
B = 89 ;
B = 144 ;
B = 233 ;
B = 377 ;
B = 610 ;
B = 987 ;
false.

Efficient Fibonacci in Prolog

1 Answers