Fibonacci

Simple non-deterministic solution in Prolog

The following Prolog code finds all the Fibonacci integers starting at zero. Ask for fib(A) and A unifies with the sequence one by one. You could argue that it should start at 1 rather than 0.

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

fib(A, B, Y) :-
    C is A + B,
    (   Y = C
    ;   fib(B, C, Y)
    ).

It has a problem however; it does not collapse neatly to semi-determinism because it unifies with Fibonacci sequence members forever in theory, or until the stack overruns in practice.

This is not an entirely useless implementation nevertheless. You can easily call it multiple times. Take the example query below. The term A unifies with the millionth Fibonacci number (a very large integer, elided below) in just over four seconds on a modest modern machine without hitting any resource limitations.

?- call_time(call_nth(fib(A), 1 000 000), B).
B = time{cpu:4.359374999999998, inferences:5999997, wall:4.443742036819458}.

The excerpt below lists an adjusted predicate formulation.

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

fib(X0, X, Y) :- Y0 is X0 + X, fib_(X, Y0, Y).

fib_(_, Y, Y).
fib_(X0, X, Y) :- fib(X0, X, Y).

It behaves identically, albeit re-factors the nested choice point.

Ordinal to Fibonacci

Defining the relationship between the sequence position and the Fibonacci integer is another approach. The following defines semi-deterministic fib/2 where mode (+, -) maps the sequence position \(N\) to the sequence integer \(F\). In this case, the positions range from \(1\) to infinity, an ordinal sequence number.

fib(1, 1) :- !.
fib(2, 1) :- !.
fib(N, F) :-
    succ(N1, N),
    fib(N1, F1),
    succ(N2, N1),
    fib(N2, F2),
    F is F1 + F2,
    !.

The predicate also excludes \(0\) from the sequence.

The first term N does not allow for a variable; succ/2 fails without at least one ground term. Hence it does not generate the sequence for N and F using query fib(N, F) non-deterministically if that exists as a requirement.

The predicate implementation also has a performance issue. It arises from the recursion. The Fibonacci at \(n\) requires the Fibonacci at \(n-1\) and \(n-2\) which each in turn queries recursively; exponential recursion. The following excerpt times the execution; printing the Fibonacci ordinal, number and number of inferences required to compute the Fibonacci number using the ordinal.

fib_inferences :-
    forall(between(1, 20, N),
           (   call_time(fib(N, F), T),
               format('~d~8|~d~16|~d~n', [N, F, T.inferences])
           )).

Results tabulate as follows. Notice the rough doubling of inferences at every increment of N. Big-O complexity approximates \(O(n^2)\), that is, quadratic complexity.

This complexity occurs because every Fibonacci requires the previous two. The implementation could reduce the complexity if it could compute arbitrary Fibonacci numbers, finding one and then finding its neighbour.

Tabling in Prolog could linearise the performance but at the cost of storage.

Accumulator with tail recursion

An accumulator can eliminate the double recursion, replacing it with a single tail recursion. Predicate fibacc/2 below counts down from N to 1 while passing the accumulated Fibonacci sum at F3 along with the preceding member of the sequence at F2.

fibacc(N, F) :-
    N > 0,
    fibacc(N, 0, 1, F).

fibacc(1, _, F, F) :- !.
fibacc(N, F1, F2, F) :-
    succ(N1, N),
    F3 is F1 + F2,
    fibacc(N1, F2, F3, F).

function fib(n)
  local function acc(n, f1, f2)
    return n == 1 and f2 or acc(n - 1, f2, f1 + f2)
  end
  return n > 0 and acc(n, 0, 1)
end

def fib(n):
    def acc(n, f1, f2):
        return n == 1 and f2 or acc(n - 1, f2, f1 + f2)
    return n > 0 and acc(n, 0, 1)

Fibonacci engines

Using an engine allows for an asynchronous stateful Fibonacci iterator. The engine starts at \(1\) and runs through the numbers for as long as required without limits or performance hits. Basic implementation below, using Prolog engines.

fib_eng :-
    engine_yield(1),
    engine_yield(1),
    fib_eng(1, 1).

fib_eng(F2, F1) :-
    F0 is F1 + F2,
    engine_yield(F0),
    fib_eng(F1, F0).

Given the two preceding Fibonacci numbers, engine predicate fib_eng/2 yields their sum and tail recurses with the sum and the last result F1. The predicate does not yield the ordinal; though easy to extend by yielding a pair. Effectively, the engine acts as an infinite generator.

Create and exercise the engine using:

engine_create(_, fib_eng, A), lazy_engine_next(A, 10, B, _).

It delivers the first ten Fibonacci numbers, unifying at term B.

Lazy lists

Yet another alternative exists. See below. The fibonacci/3 predicate transforms an incoming state to a new state and an output. In this case, state is a pair term, initially a pair of - atoms.

fibonaccis(Fibonaccis) :- lazy_list(fibonacci, - - -, Fibonaccis).

fibonacci(- - -, 0-1, 1) :- !.
fibonacci(A-B, B-C, C) :- C is A + B.

SWI Prolog has a useful engine-wrapper module called lazy_lists. Lazy lists operate as non-lazy lists (more or less) excepting that its list elements form by a background engine filling them on demand. Extract below.

?- fibonaccis(A), time(nth1(100, A, B)).
% 1,633 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
A = [1, 1, 2, 3, 5, 8, 13, 21, 34|...],
B = 354224848179261915075,

Usefully, the lazy list allows nth1/3 operations just as if the list was a fully-instantiated ground term.

Conclusions

The Fibonacci sequence is inherently recursive. Its very definition implies recursion: \(F_n=F_{n-1}+F_{n-2}\). Fibonacci at \(n\) equals the sum of the previous two. That implies that you first compute the \(n-1\) and \(n-2\) terms. Answering questions such as ‘What is the tenth Fibonacci number?’ requires an iteration of the sequence, either recursively or as a co-routine.