Why this dynamic version of Fibonacci program is incredibly faster then this other? Prolog solutions -

i learning prolog using swi prolog , have doubt followings 2 solutions of fibonacci number calculation program:

the first 1 this:

fib(1,1).    fib(2,1).      fib(n,f) :- n > 2,                   n1 n-1,               fib(n1,f1),                  n2 n-2,                   fib(n2,f2),                  f f1+f2.  

it pretty clear me hw work, simple.

then have second version that, reading code, seems work previous 1 after have calculate fibonacci number of n save in prolog database asserta/2 predicate reuse after.

so example if calculate fibonacci number 10 , 11 when go calculate fibonacci number 12 aspect use result of previous 2 computations.

so code is:

:-dynamic fibdyn/2.  fibdyn(1,1). fibdyn(2,1).  fibdyn(n,f) :- n > 2,                n1 n-1,                fibdyn(n1,f1),                n2 n-2,                fibdyn(n2,f2),                f f1+f2,                asserta(fibdyn(n,f)). 

it seems me logic same of previous one:

f fibonacci number of n if n>2 , use recursion calculate fibonacci number of n (as in preious example)

i expect program faster if ask calculate number of fibonacci number number have calculated , put database fibonacci numbers of predecessors (or of them) seems me work in strange way: fast , able directly calculate numbers of fibonacci large integers (the other version goes wrong such large numbers)

the other strange thing if trace of query obtain this:

[trace]  ?- fibdyn(200,fib).    call: (6) fibdyn(200, _g1158) ? creep    exit: (6) fibdyn(200, 280571172992510140037611932413038677189525) ? creep fib = 280571172992510140037611932413038677189525 . 

as can see seems don't execute code of fibonacci predicate directly obtain result (from where?!?!)

instad if execute query (using first version), obtain program calculate it:

[trace]  ?- fib(3,fib).    call: (6) fib(3, _g1158) ? creep ^  call: (7) 3>2 ? creep ^  exit: (7) 3>2 ? creep ^  call: (7) _g1233 3+ -1 ? creep ^  exit: (7) 2 3+ -1 ? creep    call: (7) fib(2, _g1231) ? creep    exit: (7) fib(2, 1) ? creep ^  call: (7) _g1236 3+ -2 ? creep ^  exit: (7) 1 3+ -2 ? creep    call: (7) fib(1, _g1234) ? creep    exit: (7) fib(1, 1) ? creep ^  call: (7) _g1158 1+1 ? creep ^  exit: (7) 2 1+1 ? creep    exit: (6) fib(3, 2) ? creep fib = 2 . 

why? expect second version (the 1 use asserta predicate) calculate fibonacci number 2 number , use these value generate solution of following one.

for example have following situation: i have never yet calculate fibonacci number , ask calculate fibonacci number of n=4 calculate (as in second posted stacktrace).

so ask calculate fibonacci number of n=5 , use fibonacci of n=4 saved. ask calculate fibonacci number of n=6 , use saved fibonacci number of 4 , of 5

what missing? can me understand?

tl;dr: use retractall erase asserted facts memory.

change definition

:- dynamic fibdyn/2. :- retractall( fibdyn(_,_) ).  %% without this, you'll retain previous                                 %% facts if reload program fibdyn(1,1). fibdyn(2,1).  fibdyn(n,f) :- n > 2,                n1 n-1,                fibdyn(n1,f1),                n2 n-2,                fibdyn(n2,f2),                f f1+f2,                asserta( (fibdyn(n,f):-!) ). 

notice cut inside asserted rule. notice the retractall statement. without it, asserted facts remain in memory if reload program. that's probably reason why getting results immediately.

after you've run e.g. ?- fibdyn(10,x) once, can see asserted facts in database:

12 ?- listing(fibdyn). :- dynamic fibdyn/2.  fibdyn(10, 55) :- !. fibdyn(9, 34) :- !. fibdyn(8, 21) :- !. fibdyn(7, 13) :- !. fibdyn(6, 8) :- !. fibdyn(5, 5) :- !. fibdyn(4, 3) :- !. fibdyn(3, 2) :- !. fibdyn(1, 1). fibdyn(2, 1). fibdyn(a, d) :-         a>2,         b a+ -1,         fibdyn(b, e),         c a+ -2,         fibdyn(c, f),         d e+f,         asserta((fibdyn(a, d):-!)).  true. 

that why runs fast. difference in speed you're seeing the difference between exponential , linear time complexity algorithm.

next time call it, has access calculated results:

[trace] 15 ?- fibdyn(10,x).    call: (6) fibdyn(10, _g1068) ? creep    exit: (6) fibdyn(10, 55) ? creep x = 55.  [trace] 16 ?-  

this explains fibdyn(200,x) call trace output. you've tried after you've calculated once or twice before.

here's happens when next request 11th number:

[trace] 35 ?- fibdyn(11,x).    call: (6) fibdyn(11, _g1068) ? creep    call: (7) 11>2 ? creep    exit: (7) 11>2 ? creep    call: (7) _g1143 11+ -1 ? creep    exit: (7) 10 11+ -1 ? creep    call: (7) fibdyn(10, _g1144) ? creep    exit: (7) fibdyn(10, 55) ? creep    call: (7) _g1146 11+ -2 ? creep    exit: (7) 9 11+ -2 ? creep    call: (7) fibdyn(9, _g1147) ? creep    exit: (7) fibdyn(9, 34) ? creep    call: (7) _g1068 55+34 ? creep    exit: (7) 89 55+34 ? creep ^  call: (7) asserta((fibdyn(11, 89):-!)) ? creep ^  exit: (7) asserta((fibdyn(11, 89):-!)) ? creep    exit: (6) fibdyn(11, 89) ? creep x = 89.  [trace] 36 ?-  

and again:

[trace] 36 ?- fibdyn(11,x).    call: (6) fibdyn(11, _g1068) ? creep    exit: (6) fibdyn(11, 89) ? creep x = 89.