NOMBRE DE FIBONACCI

Messages postés
4
Date d'inscription
samedi 15 mars 2003
Statut
Membre
Dernière intervention
6 septembre 2007
-
Messages postés
4
Date d'inscription
samedi 15 mars 2003
Statut
Membre
Dernière intervention
6 septembre 2007
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/17177-nombre-de-fibonacci

Messages postés
4
Date d'inscription
samedi 15 mars 2003
Statut
Membre
Dernière intervention
6 septembre 2007

J'ai deux petites questions
- tu peux aller jusque combien avant qu'il y est le probleme de calcul modulo 2^32 ?
- ça met combien de temps ?

Sinon, il y a une méthode pour accélérer le tout de facon draconnienne (complexité en log(n) au lieu de n)
- on remarque que [[0,1][1,1]]^n a pour element en bas à droite fibo(n)
- pour calculer a^n efficacement ,on utilise
a^(2*p)=(a*a)^p et a^(2*p+1)=a*((a*a)^p)

Ca accelere vraiment (epoustouflant sur une calculatrice TI-92), sauf que sur PC, il faudrait passer en int64 pour atteindre des grandes valeurs et voir la différence

C'est à tester