cubbi.com: fibonacci numbers in prolog
Prolog
Date: 1971 (Standardized in ISO/IEC 13211-1:1995)
Type: Logic programming language
Usage: artificial intellect, fuzzy logic, natural language processing, etc. It's a research language.

ALGORITHM 1A: NAIVE BINARY RECURSION
% This program calculates the nth fibonacci number
% using alrogirhtm 1A: naive binary recursion
%
% compiled: swipl -q -O -t main -o f1a -c f1a.pl
% executed: ./f1a n

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% It follows naive recursion recursion: F(n) = F(n-1) + F(n-2)
fib(0,0).
fib(1,1).
fib(N,F) :-
   succ(N1,N), succ(N2,N1), fib(N1,F1), fib(N2,F2), plus(F1,F2,F).

% support negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fib(AN,FP), F is FP * (sign(N) ** (N+1)).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f1a N" is "pl -x f1a -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in usage printout and exit
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f1a <n>\n').

ALGORITHM 1B: CACHED BINARY RECURSION
% This program calculates the nth fibonacci number
% using alrogirhtm 1B: cached binary recursion
%
% compiled: swipl -q -O -t main -o f1b -c f1b.pl
% executed: ./f1b n
%
% Predicate fib(N,F) is true if N'th Fibonacci number is F. 
% It follows naive recursion recursion: F(n) = F(n-1) + F(n-2), but uses simple
% tabling (Prolog slang for memoization) approach borrowed from
% a comp.lang.prolog post by Bart Demoen
:- dynamic tabled_fib/2.
fib(N,F) :- tabled_fib(N,F), !.
fib(N,F) :- work_fib(N,F), assert(tabled_fib(N,F)).
work_fib(0,0).
work_fib(1,1).
work_fib(N,F) :- succ(N1,N), succ(N2,N1), fib(N1,F1), fib(N2,F2), plus(F1,F2,F).

% support negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fib(AN,FP), F is FP * (sign(N) ** (N+1)).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f1b N" is "pl -x f1b -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f1b <n>\n').

ALGORITHM 2A: CACHED LINEAR RECURSION
% This program calculates the nth fibonacci number
% using alrogirhtm 2A: cached linear recursion
%
% compiled: swipl -q -O -t main -o f2a -c f2a.pl
% executed: ./f2a n

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% it sets the first two values of the list, calculates the number,
% takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fiblist(AN,[FP|_]), F is FP* sign(N) ** (N+1).

% fiblist(N, L) is true if L is the list of the first N fib numbers.
fiblist(0, [0]).
fiblist(1, [1,0]).
fiblist(N, [F2,F1,F0|L]) :- succ(NP,N), fiblist(NP, [F1,F0|L]), plus(F0,F1,F2).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f2a N" is "pl -x f2a -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f2a <n>\n').

ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATOR
% This program calculates the nth fibonacci number
% using alrogirhtm 2B: linear recursion with accumulator
%
% compiled: swipl -q -O -t main -o f2b -c f2b.pl
% executed: ./f2b n

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% it sets the initial values for the recursive function's accumulator and
% takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), l(0,1,AN,FP), F is FP* sign(N) ** (N+1).

% Predicate l(F1,F2,N,F) recursively calculates N'th Fiboacci number
% using parameters F1 and F2 as accumulator
l(F1,F2,N,F):-
    N < 1, F is F1;
    plus(F1,F2,F3), succ(N2,N), l(F3,F1,N2,F).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f2b N" is "pl -x f2b -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f2b <n>\n').

ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES
% This program calculates the nth fibonacci number
% using alrogirhtm 2C: imperative loop with mutable variables
%
% compiled: swipl -q -O -t main -o f2c -c f2c.pl
% executed: ./f2c n

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% it sets the initial variables for the loop and
% takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   nb_setval(x1, 0), nb_setval(x2, 1),
   AN is abs(N), fibloop(AN,FP), F is FP* sign(N) ** (N+1).

% loop using SWI Prolog's global mutable variables:
% if N is zero, return x1, otherwise x1=x1+x2 and x2=previous x1 and N=N-1
fibloop(N,F) :-
   N < 1, nb_getval(x1,F);
   nb_getval(x1,A), nb_getval(x2,B), plus(A,B,SUM),
   nb_setval(x1,SUM), nb_setval(x2,A), succ(NP,N), fibloop(NP,F).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f2c N" is "pl -x f2c -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f2c <n>\n').

ALGORITHM 3A: MATRIX MULTIPLICATION
% This program calculates the nth fibonacci number
% using alrogirhtm 3A: matrix multiplication
%
% compiled: swipl -q -O -t main -o f3a -c f3a.pl
% executed: ./f3a n

% must load explicitly or SWI will auto-load transpose/2 from ugraphs
:- use_module(library(clpfd)).

% N is the dot product of lists V1 and V2.
dot(V1, V2, N) :- maplist(product,V1,V2,P), sumlist(P,N).
product(N1,N2,N3) :- N3 is N1*N2.

% Matrix multiplication with matrices represented
% as lists of lists. M3 is the product of M1 and M2
mmult(M1, M2, M3) :- transpose(M2,MT), maplist(mm_helper(MT), M1, M3).
mm_helper(M2, I1, M3) :- maplist(dot(I1), M2, M3).

% Predicate mp(N,M,R) is true if R is M raised to the Nth power for N>0
% It uses exponentiation by repeated squaring
mp(N,M,M) :- N < 2.
mp(N,M,R) :- T2 is N mod 2, T is N//2, mp(T,M,C),
    ( T2 =:= 0, mmult(C,C,R); mmult(C,C,C2), mmult(C2,M,R) ), !.

% Predicate fib(N,F) is true if N'th Fibonacci number is F.
% it raises the matrix [1,1],[1,0] to n-1st power
fib(N, F) :-
   N < 1, F = 0;
   succ(NP,N), mp(NP, [[1,1],[1,0]], [[F,_],_]).

% this takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fib(AN,FP), F is FP* sign(N) ** (N+1).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f3a N" is "pl -x f3a -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f3a <n>\n').

ALGORITHM 3B: FAST RECURSION
% This program calculates the nth fibonacci number
% using alrogirhtm 3B: fast recursion
%
% compiled: swipl -q -O -t main -o f3b -c f3b.pl
% executed: ./f3b n

% predicate fib calculates the nth fibonacci number according to
% the recurrent relationship: 
% F(2n-1) = F(n-1)^2 + F(n)^2
% F(2n) = (2F(n-1) + F(n))F(n)
% here, k1 = F(n-1), k2 = F(n), k3 = F(n+1)
fib(0, [0,0]).
fib(1, [1,0]).
fib(N, [F1,F2]) :-
     T2 is N mod 2, T is N // 2, fib(T, [K2, K1]), plus(K1,K2,K3),
    (T2 =:= 0, F1 is (K1+K3)*K2, F2 is K1^2+K2^2;
               F1 is K3^2+K2^2, F2 is (K1+K3)*K2 ), !.

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% it sets the initial values for the recursive function's accumulator and
% takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fib(AN,[FP,_]), F is FP* sign(N) ** (N+1).

% Predicate l(F1,F2,N,F) recursively calculates N'th Fiboacci number
% using parameters F1 and F2 as accumulator
l(F1,F2,N,F):-
    N < 1, F is F1;
    plus(F1,F2,F3), succ(N2,N), l(F3,F1,N2,F).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f3b N" is "pl -x f3b -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f3b <n>\n').

ALGORITHM 3C: BINET'S FORMULA WITH ROUNDING
% This program calculates the nth fibonacci number
% using alrogirhtm 3C: Binet's formula with rounding
%
% compiled: swipl -q -O -t main -o f3c -c f3c.pl
% executed: ./f3c n

% predicate fib calculates the nth fibonacci number according to
% Binet's formula with rounding:
% F = round ( phi^(n-1)/sqrt(5) )
% SWI Prolog does not have arbitrary precision floating-point numbers,
% the maximum correct result on my system is F(70)
fib(N, F) :-
    Phi is (1+5**0.5)/2, 
    F is round(Phi**N/(5**0.5)).

% Predicate f(N,F) is true if N'th Fibonacci number is F.
% it sets the initial values for the recursive function's accumulator and
% takes care of the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f(N,F) :-
   AN is abs(N), fib(AN,FP), F is FP* sign(N) ** (N+1).

% Predicate fib_print(N) prints the n'th Fibonacci number.
fib_print(N) :-
   write(N), write('th Fibonacci number is '), f(N,X), write(X), nl.

% main/0 is the entry point for this module 
% it reads the command line, checks its length, 
% (swi prolog command line for "./f3c N" is "pl -x f3c -- N")
% then it converts the last commandline argument to a number,
% and executes fib_print(N). Any failure (wrong command line length
% or failed string to number conversion) results in Usage bring printed
main :-
   current_prolog_flag(argv,A), length(A, AL),
   AL =:= 5, last(A, M), catch(atom_number(M,N),_,fail), fib_print(N) ;
   write('Usage: f3c <n>\n').