%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% fib.pl
% 
% Prolog implementation of fib that runs in linear time.
% Author: Ramin Rakhamimov
% http://raminrakhamimov.com
% ramin32 AT gmail DOT com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fib(0,0).
fib(1,1).
fib(2,2).
fib(F,R) :- fib(F,3,1,2,R).

fib(F,F,_,Y,R) :- R is Y, !.
fib(F,I,X,Y,R) :-
  I1 is I + 1,
  X1 is Y,
  Y1 is X + Y,
  fib(F,I1,X1,Y1,R).