Thierry Loiseau a écrit :Bon. Et comment déduis-tu cela ?
2.5550
Je ne veux pas répondre à la place de
franck196569, mais clairement son algorithme est basé sur une décomposition en fractions continues, (les registre H et I des lignes 1 et 4) fractions continues que l'on détermine pas à pas jusqu'à obtenir une valeur suffisamment proche du réel initial
x (cf. test ligne 6).
Ce qui est malin c'est que la fraction est exprimée à chaque pas sous la forme d'une somme de deux fractions dont on détermine le numérateur (registres A,B et E,F) et le dénominateur par inversions successives de ceux-ci (ligne 5).
Ce qui fait que dès que l'on estime être assez proche du nombre réel initial, il suffit d'afficher la fraction finale (ligne 7)
Je connaissait cet algorithme, mais avec un tableau intermédiaire (qui mémorise les a(i) des fractions continues) construit à partir de X (décomposition), puis une seconde partie effectuait les calcul des numérateur et dénominateur à partir des valeurs du tableau intermédiaire (recomposition).
Le code proposé par
franck est plus malin car il combine les deux étapes.
Pour 2.555 (ou 2.5550 d'ailleurs), on obtient la décomposition en fraction continue et recomposition en fraction simple suivante:
Code : Tout sélectionner
2.555 = 2. + 1/( 1/.555 )
2.555 = 2. + 1/( 1.8018 )
2.555 = 2. + 1/( 1. + 1/( 1/.801801 ))
2.555 = 2. + 1/( 1. + 1/( 1.2471910 ))
2.555 = 2. + 1/( 1. + 1/( 1. + 1/( 1/.2471910 )))
2.555 = 2. + 1/( 1. + 1/( 1. + 1/( 4.04545454 )))
2.555 = 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 1/.04545454 ))))
2.555 = 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 21.99999828 ))))
2.555 = 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 21. + 1/( 1/.99999828 ))))) etc.
2.555 = [ 2. 1. 1. 4. 21. 1. . . . ]
Code : Tout sélectionner
2.555 ≈ [ 2. 1. 1. 4. 21. 1. ]
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 21. + 1/( 1. / 1. )))))
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 21. + 1/ 1.))))
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 1/( 4. + 1/( 22 ))))
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 1/((88.+ 1)/22)))
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 1/( 89/22 )))
2.555 ≈ 2. + 1/( 1. + 1/( 1. + 22/89 ))
2.555 ≈ 2. + 1/( 1. + 1/((89. + 22)/89))
2.555 ≈ 2. + 1/( 1. + 1/( 111/89 ))
2.555 ≈ 2. + 1/( 1. + 89/111 )
2.555 ≈ 2. + 1/((111. + 89)/111 )
2.555 ≈ 2. + 1/( 200/111 )
2.555 ≈ 2. + 111 / 200
2.555 ≈(400. + 111)/ 200
2.555 ≈ 511 / 200
Le point central est l'approximation 1/.99999828 ≈ 1 qui permet de retrouver le résultat du code (qui utilise 1E-9).
Selon l'approximation utilisée, on obtiendra bien évidemment des fractions simples différentes. Les plus grands numérateurs et dénominateurs permettant des valeurs approchées plus proches de la valeur exacte.
Notons que dans certains cas, la suite de fraction continue s'arrête notamment lorsque qu'un inverse produit un entier. Dans ce cas, la valeur des fractions continues et de la fraction simple qui en découle produisent la valeur exacte.
Par exemple
Code : Tout sélectionner
0.5 = 0. + 1/( 1/.5 ) = [ 0. 2. ] = 0. + 1/2. = 1 / 2
3.5 = 3. + 1/( 1/.5 ) = [ 3. 2. ] = 3. + 1/2. = 7 / 2
2.555 permet d'illustrer l'importance de la série de fraction continue à retenir pour correctement approximer le résultat :
Code : Tout sélectionner
2.555 ≈ [ 2.] = 2 / 1 = 2.
2.555 ≈ [ 2. 1.] = 3 / 1 = 3.
2.555 ≈ [ 2. 1. 1.] = 5 / 2 = 2.5
2.555 ≈ [ 2. 1. 1. 4.] = 23 / 9 = 2.5555555555555555555555555
2.555 ≈ [ 2. 1. 1. 4. 21.] = 488 / 191 = 2.554973821989528795811518
2.555 ≈ [ 2. 1. 1. 4. 21. 1.] = 511 / 200 = 2.555
2.555 ≈ [ 2. 1. 1. 4. 21. 1. 581395.] = 297093333 / 116279191 = 2.55499999999570000448317532
2.555 ≈ [ 2. 1. 1. 4. 21. 1. 581395. 2.] = 594187177 / 232558582 = 2.554999999995700008181164
2.555 ≈ [ 2. 1. 1. 4. 21. 1. 581395. 2. 1.] = 891280510 / 348837773 = 2.554999999957000069485021
2.555 ≈ [ 2. 1. 1. 4. 21. 1. 581395. 2. 1. 6.] = 5941870237 / 23225585220 = 2.55499999995700007071