Thank you for these benchmarks! For a fair comparison, one should however also take into account that SWI-Prolog is among the slower Prolog systems. I therefor

Thank you for these benchmarks! For a fair comparison, one should however also take into account that SWI-Prolog is among the slower Prolog systems. I therefore recommend to also use a faster Prolog system. For example, I used the following Prolog translation of your code and ran it in GNU Prolog: n_fib(N0, F) :- ( N0 =< 1 -> F = 1 ; N1 is N0 - 1, N2 is N0 - 2, n_fib(N1, F1), n_fib(N2, F2), F is F1 + F2 ). On my machine configuration, GNU Prolog is more than thrice as fast as SWI-Prolog (even with -O) for: | ?- n_fib(38, F). F = 63245986 GNU Prolog in fact compiles to native code. You can test this by putting the code into a file, say fib.pl, and compiling it with the GNU Prolog compiler using: $ gplc fib.pl You can then run it with ./fib and invoke the above query.