1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%% 16 June 2003 Bart Demoen, Tom Schrijvers, K.U.Leuven
4%%
5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6
7:- module(fibonacci,[main/0,main/1]).
8
9:- use_module(library(chr)).
10
11:- constraints fibonacci/2.
12
13%% fibonacci(N,M) is true iff  M is the Nth Fibonacci number.
14
15%% Top-down Evaluation with effective Tabulation
16%% Contrary to the version in the SICStus manual, this one does "true"
17%% tabulation
18
19fibonacci(N,M1) # ID \ fibonacci(N,M2) <=> var(M2) | M1 = M2 pragma passive(ID).
20
21fibonacci(0,M) ==> M = 1.
22
23fibonacci(1,M) ==> M = 1.
24
25fibonacci(N,M) ==>
26	N > 1 |
27		N1 is N-1,
28		fibonacci(N1,M1),
29		N2 is N-2,
30		fibonacci(N2,M2),
31		M is M1 + M2.
32
33main :-
34	main(2000).
35
36main(N):-
37	cputime(X),
38	fibonacci(N,_),
39	cputime( Now),
40	Time is Now-X,
41	write(bench(fibonacci ,N,Time, 0, hprolog)),write('.'), nl.
42
43