Re: Comment casser le mythe de rapidité de Fibonacci :-)

ouais enfin bon le meilleur moyen ça reste d'utiliser le bon algorithme, à savoir celui en log(n) appels récursifs.

en chameau, en utilisant la bibliothèque de calculs avec les grands nombres, ça donne ceci:

open Num

let pmul (a, b) (c, d) =
let ac = a */ c in
(ac +/ a */ d +/ b */ c,
ac +/ b */ d)

let rec pow x a n =
if n = 0
then a
else
pow
(pmul x x)
(if n mod 2 = 0 then a else pmul a x)
(n / 2)

let fib n =
if n < 0 then invalid_arg "fib" ;
fst (pow (Int 1, Int 0) (Int 0, Int 1) n)

let _ =
print_endline (string_of_num (fib 100000))


Pour cacluler fib(100000) chez moi ça va ×ばつ plus vite qu'avec l'algo linéaire.