/*

	File: 		fibonacci.chr
	Author:		Bart Demoen, Tom Schrijvers
	E-mail:		Tom . Schrijvers @ cs . kuleuven . be
	Copyright:	2003 - 2004, K.U.Leuven

	Computes Fibonacci numbers
	
*/

:- module(fibonacci,[main/0,main/1]).

:- use_module(library(chr)).

handler fibonacci.

constraints fibonacci/2.

%% fibonacci(N,M) is true iff  M is the Nth Fibonacci number.

%% Top-down Evaluation with effective Tabulation
%% Contrary to the version in the SICStus manual, this one does "true"
%% tabulation

fibonacci(N,M1) # ID \ fibonacci(N,M2) <=> var(M2) | M1 = M2 pragma passive(ID).

fibonacci(0,M) ==> M = 1.

fibonacci(1,M) ==> M = 1.

fibonacci(N,M) ==>
	N > 1 | 
		N1 is N-1,
		fibonacci(N1,M1),
		N2 is N-2,
		fibonacci(N2,M2),
		M is M1 + M2.

main :-
	main(1500).

main(N):-
	statistics(runtime,[X|_]),
	loop(N),
	statistics(runtime,[ Now|_]),
	Time is Now-X,
	write(bench(fibonacci,N,Time,0,sicstus)),write('.'),nl.

loop(N) :-
	( N > 0 ->
		( fibonacci(41,_), fail ; true),
		M is N - 1,
		loop(M)
	;
		true
	).