fib(0,0).
fib(1,1).
fib(N,F):-
	N > 1,
	N1 is N- 1,
	N2 is N1 - 1,
	fib(N1,F1),
	fib(N2,F2),
	F is F1 + F2.

%***********************************************************************

lfib(N,F) :- lemma_fib(N,F),!.
lfib(N,F) :-
	N > 1,
	N1 is N - 1,
	N2 is N1 - 1,
	lfib(N1,F1),
	lfib(N2,F2),
	F is F1 + F2,
	assert(lemma_fib(N,F)).

:- dynamic lemma_fib/2 .
/* without this declaration
ERROR: No permission to modify static_procedure `lemma_fib/2'
*/
lemma_fib(0,0).
lemma_fib(1,1).

%***********************************************************************

afib(N,F) :- forwardfib(2,N,1,1,F).
/* forwardfib(M,N,F1,F2,F) F1 and F2 are the (M-1)th and the Mth fibonacci number
*/
forwardfib(M,N,F1,F2,F2) :- M >= N.
forwardfib(M,N,F1,F2,F) :- M < N,
	NextM is M + 1,
	NextF is F1 + F2,
	forwardfib(NextM,N,F2, NextF,F).

%***********************************************************************
/*
?- lfib(24,F).

F = 46368 ;

No
?- fib(24,L).
ERROR: Out of local stack


?- time(fib(21,L)).
% 106,261 inferences, 1.01 CPU in 1.01 seconds (100% CPU, 105209 Lips)

L = 10946 ;

No
?- time(lfib(21,L)).
% 182 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)

L = 10946 ;

No
?- 
*/
%***********************************************************************
/*

?- lfib(1477,L).
ERROR: Arithmetic: evaluation error: `float_overflow'
^  Exception: (8) _G158 is 1.30699e+308+8.07764e+307 ? Unknown option (h for help)
?- time(lfib(1475,L)).
% 13,268 inferences, 0.01 CPU in 0.01 seconds (174% CPU, 1326800 Lips)

L = 8.07764e+307 ;

?-  time(afib(1475,L)).
% 8,841 inferences, 0.01 CPU in 0.00 seconds (408% CPU, 884100 Lips)

L = 8.07764e+307 ;

*/