Merci pour cette formule de Bernouilli qui est la bienvenue car elle explique bien pourquoi il s'agit de nombres rationnels.
Pour commencer simplement, je présenterais un premier bout de code , pour HP28S (mais utilisant uniquement du RPL simple et compatible à toute la famille des HP28 à HP50).
Ce premier programme permet de calculer sans arrondi les nombre de Fibonacci pour n allant de 2 à 59 :
Code : Tout sélectionner
« -> n
« 0 // F0 soit F(n-1) pour n=1
1 // F1 soit F(n) pour n=2
2 n START // Calcul des F(n) pour n>1 par iteration
DUP ROT + // F(n+1) <-- F(n-1) + F(n)
NEXT
SWAP DROP // efface F(n-1) pour ne laisser que le résultat F(n)
»
»
'FIB' STO
prend
n dans la pile et le remplace par
F(n).
En RPL c'est assez simple, il suffit dans la boucle de calcul de laisser les nombres F(n-1) et F(n) et de calculer F(n+1) en faisant disparaitre F(n-1) de la pile.
Cette version ne fonctionne pas pour n=0 mais peu importe, on cherche à aller vers les grand n.
Avec ce programme, LAST retourne l'élément F(n-1), ce qui peut être utile pour implémenter le calcul des éléments suivant sans reprendre l'itération depuis le début.
Inconvénient, à partir de n=60, les 12 chiffres de mon HP28S ne sont plus suffisants pour représenter F(n) complètement (manque les derniers chiffres !).
Donc l'avantage principal que je trouve à cet algorithme est qu'il permet facilement d'obtenir F(n) avec tous les chiffres par une très simple modification:
Code : Tout sélectionner
« -> n
« [0 0 0 0 0 0 0 0] // F0 soit F(n-1) pour n=1
[0 0 0 0 0 0 0 1] // F1 soit F(n) pour n=2
2 n START // Calcul des F(n) pour n>1 par iteration
DUP ROT + // F(n+1) <-- F(n-1) + F(n)
ACarry // Reporte les retenues
NEXT
SWAP DROP // efface F(n-1) pour ne laisser que le résultat F(n)
»
»
'AFIB' STO
prend
n dans la pile et le remplace par le vecteur [
F(n) ] composé de huit éléments donnant tout les chiffres de
F(n).
L'algorithme est fondamentalement le même, on obtient les F(n) par itérations en maintenant les termes F(n-1) et F(n) dans la pile.
Le HP28 permet d'additionner les vecteurs membre à membre pour peu qu'ils soient de la même dimension.
Seule ombre au tableau, cette adition ne tient pas compte du dépassement de capacité de chaque élément. C'est à dire qu'il faut 'manuellement' veiller à ce que le résultat de chaque somme ne dépasse pas la capacité maximale des 12 chiffres.
C'est le rôle de ACarry, qui dès qu'un des éléments du vecteur F(n) dépasse 1E11, l'arrondi et reporte le surplus dans le membre de gauche en tant qu'unité.
C'est en fait tout simplement le principe de la retenue que nous utilisons pour toute opération posée sur le papier.
Code : Tout sélectionner
« 0 SWAP // Initialise la retenue à zéro
8 1 FOR i // Parcours le vecteur de droite à gauche
i DUP2
GET // Elément i de F(n)
4 ROLL + // Ajoute la retenue précèdante (ou zéro à défaut)
1E11 MOD // Arrondi à 1E11
LAST / IP // Calcul la retenue suivante
4 ROLLD // Replace la retenue dans la pile
PUT // Replace l'élément arrondi à sa position dans le vecteur F(n)
-1 STEP
IF SWAP THEN ERROR END // Si dernière retenue non nulle, alors erreur de dépassement
»
'ACarry' STO
Transforme le vecteur
[ x8 x7 x6 x5 x4 x3 x2 x1] en vecteur
[ e8 e7 e6 e5 e4 e3 e2 e1] dont tous les éléments sont des entiers de 11 chiffres au maximum.
Ex: [0 0 0 0 0 0 23 123456789012] ---> [0 0 0 0 0 0 24 23456789012]
C'est avec ce code, qu'en quelques minutes, on arrive à afficher toutes les décimales de F(400):
400 AFIB returns [ 1760236 80645013966 46822694539 24112507703 84383304492 19188672599 28965753450 44216019675]
Voilà qui est fort intéressant mais qui ne répond pas entièrement à la question, qui sous-entendait une réponse en binaire et graphique.
Ce qui sera l'occasion d'un prochain post.
Bonsoir à tous !
