Un reste, loin dans la suite de Fibonacci

mai 4, 2020 Libremaths Laisser un commentaire

Épisode 1 : ça parle de quoi cet article ?

Le plus simple est que je vous le raconte en vidéo 😉

Petite remarque: dans cette vidéo je donne un ordre de grandeur du nombre de chiffres de $F_N$ . Mais en fait en notant $r=\frac{\ln\phi}{\ln10}$ , en majorant $\ln(1+x)$ par $x$ (pour $x>0$ ), on obtient assez facilement

$nr-\frac{\ln5}{2\ln10}-2^{-n}<x<nr-\frac{\ln5}{2\ln10}+2^{-n}$

Pour $n=N=10^{18}$ on obtient au dixième près

$x\sim208987640249978733,8$

ce qui montre que $F_{N}$ possède exactement $208987640249978734$ chiffres.

Épisode 2 : si on essayait …

…malgré tout de coder le calcul des termes dans un langage compilé ? (ou encore: si je trouvais un prétexte pour jouer avec le langage Ada ?)

Première partie :

Deuxième partie :

Troisième épisode : les maths à la rescousse !

Un peu d’algèbre linéaire et la fameuse « exponentiation rapide ». Un algorithme qui décoiffe 🙂

Quatrième épisode : encore des maths !

Mais là, on part dans le monde de l’arithmétique modulaire pour appliquer l’algorithme d’exponentiation rapide

Épilogue

On implémente tout ce qu’on a vu en Ada pour donner une réponse instantanée à notre problème

LibreMaths