:- module(_,_).

% - Direct definition of the Fibonacci sequence:

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.

% - Asserting results that have been found true (lemmas):

:- dynamic lemma_fib/2.

lemma_fib(0, 0).
lemma_fib(1, 1).

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)).

% - To measure `lfib/2` from scratch, the table is emptied first:

lfib_fresh(N, F) :-
    retractall(lemma_fib(_, _)),
    assert(lemma_fib(0, 0)),
    assert(lemma_fib(1, 1)),
    lfib(N, F).

%   Try:
% ?- speedup(fib(24,_), lfib_fresh(24,_)).

%   The speedup grows with `N`:
% ?- speedup(fib(30,_), lfib_fresh(30,_)).

%   If the table is not emptied, `lfib/2` just finds the result in it:
% ?- speedup(fib(24,_), lfib(24,_)).

% - `speedup/2` runs the two goals and compares their times, as in
%   the first example (`010_swap.pl`).

%! \begin{hide}
speedup(Slow, Fast) :-
    speedup_loop(true, Slow, Fast).

speedup_loop(Loop, Slow, Fast) :-
    time_of(Loop, Slow, TS),
    time_of(Loop, Fast, TF),
    show_speedup(TS, TF).

time_of(Loop, Goal, T) :-
    repeat_time(1, Loop, Goal, T).

repeat_time(N, Loop, Goal, T) :-
    loop_time(N, Goal, TG),
    (   TG >= 100
    ->  loop_time(N, Loop, TL),
        (   TG - TL > TG / 10        % (else too fast to tell
        ->  T is (TG - TL) / N       %  from the loop itself)
        ;   T = 0
        )
    ;   N1 is N * 10,
        repeat_time(N1, Loop, Goal, T)
    ).

loop_time(N, Goal, T) :-
    statistics(runtime, [T0, _]),
    ( between(1, N, _), once(Goal), fail ; true ),
    statistics(runtime, [T1, _]),
    T is T1 - T0.

show_speedup(TS, TF) :-
    format("Slow: ", []), show_time(TS),
    format(", fast: ", []), show_time(TF),
    (   TS > 0, TF > 0
    ->  S is TS / TF,
        format(", speedup: ~1f~n", [S])
    ;   nl
    ).

show_time(T) :-
    T > 0, !,
    format("~4f ms", [T]).
show_time(_) :-
    format("too fast to measure", []).

:- use_module(library(between)).
%! \end{hide}