Fibonacci de 50 : hors de portée en version naïve
Calculer fib(50) naïvement demande plus de 40 milliards d'appels : environ 13 minutes.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Valeur de F(50)
- 12 586 269 025
- Appels de la version récursive naïve
- 40 730 022 147
- Appels avec mémorisation
- 99
- Additions de la version itérative
- 49
- Durée de la version naïve
- 13 min 35 s
Le cas en détail
F(51) vaut 20 365 011 074, soit environ 40 milliards d'appels. Il faudrait plusieurs minutes pour un résultat que la version mémorisée donne en 99 appels. C'est le meilleur exemple pour justifier la mémorisation.
À retenir : Le gain ne vient pas d'un ordinateur plus rapide, mais d'un meilleur algorithme.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Rang n (0 à 200) : 50
- Appels de fonction par seconde : 50000000
- Valeur de F(50)
- 12 586 269 025
- Appels de la version récursive naïve
- 40 730 022 147
- Appels avec mémorisation
- 99
- Additions de la version itérative
- 49
- Durée de la version naïve
- 13 min 35 s
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
Avec fib(0) = 0 et fib(1) = 1, le nombre d'appels C(n) vérifie C(n) = 1 + C(n-1) + C(n-2), ce qui donne C(n) = 2 F(n+1) - 1. Avec mémorisation, chaque valeur n'est calculée qu'une fois : 2n - 1 appels. La version itérative fait n - 1 additions.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.