Misez p'tit Optimisez n°98 : La saison des nombres et fractions périodiques

[C.Ret]

Ah! L'automne, qui est doux de voir le vent emporter les feuilles jaunies en tourbillons sous le ciel teinté de bleu et parsemé de nuages gris menaçants mais encore entre découpés par de lumineux rayons d'un soleil encore présent...





Qu'il est bon de pouvoir rester chez soi à l'abri des intempéries... et de tous ces arbres qui se fractionnent sous l'effet des courants d'air...

Toutes ces feuilles sont comme les décimales des nombres qui s'égrainent à l'infini, ou non d'ailleurs.
Ces paysages dorées et en décomposition laisse mon esprit chagrin s'abandonner dans d'infinies rêveries et une douce poésie où les feuilles s'égrainnes en multitude de chiffres...

Exactement comme le tableau ci-dessous :




Heureusement, il y a sur notre forum des sujets assez récents dont l'excellant MPO n°97 anniversaire et d'autres un peu plus anciens, sans compter les vidéo de certains membres et autres indices qui, comme les feuilles éparpillées sur le sol, parsèment notre forum d'indices.

Il nous sera donc facile de composer sur nos pockets, assistants numériques et autres calculatrices les outils qui nous permettrons, comme le vents qui à cette période de l'année égraine les feuilles des arbres, égrainer les décimales des nombres fractionnaires et décimaux, périodiques ou finis (et éventuellement les rationnels dans la limite des capacité de nos machines) et les rassembler en fractions irréductibles et irréprochables.


Evidemment, je vous laisse le choix d'accommoder comme bon vous semble cette opération en un ou plusieurs programmes ou sous-programmes et d'afficher ou d'imprimer les résultats sur vos machines et engins comme cela conviendra le mieux pour obtenir un code efficace, court et suffisamment rapide pour avoir un résultat dans l'heure.
Vous pouvez et devais bien évidemment tirer partie des instructions et commandes de votre machine et trouver la solution la plus pratique pour indiquer les feuilles qui se répètent à l'infini (ou à défaut la quantité qui se répètent à la fin de l'arbre).

Si vous utiliser des instructions et commande spécifique à vos système, merci de bien nous expliquer leur fonctionnement. Je suis de nature curieuse et toujours avide de savoir comment les autres font.



En attendant, je profite de l'accalmie et de ces quelques rayons solaires pour aller ramasser les chiffes mortes qui se sont accumulées au pied de la porte et qui vont finir par boucher l'avaloir en bas de la descente du garage. Je vais les rassembler en deux fractions que les agents municipaux ramasseront demain matin.

[Gilles59]

Ah! Un nouveau MPO!

J'ai une solution élégante pour HP50g mais je laisse tout le monde chercher un peu ;D

[gege]

Bonjour,
Oulàlààà je ne comprends pas ce qu'il faut faire.
Convertir des nombres en fractions ?
Trouver les périodes de répétitions des décimales de fractions ?
Convertir des périodes de répétitions de décimales en nombres ?
Explications s'il vous plaît !
Sinon, bien psychédélique comme on les aime ce MPO
G.E.

[C.Ret]

Oui, pardon, c'est vrai que ma phrase est un peu tarabiscotée et peu claire.

Il faut simplement transformer les nombres en fractions.

Par exemple 0,5 en 1/2.

Rien n'est imposé, on peut proposer un ou plusieurs programmes afin de convertir les nombres décimaux qu'ils soient périodiques ou non.
On peut aussi, comme on le souhaite présenter le résultat sous forme d'une fraction avec ou sans partie entière séparée, voir même ne pas afficher de fraction mais simplement avoir les résultats affichés ou imprimés comme on le veut (ou le peut sur les système les plus rustres).

La seule contrainte, est de bien expliquer, pour chaque machine et programme, comment utiliser tout cela afin d'avoir un résultat correct (c'est à dire une fraction qui donne exactement la valeur du nombre).

Et aussi, faire plus court, mieux organisé, plus pratique ou plus rapide que ses rivaux !

[gege]

Bonjour,
Ok c'est clair.
Attention, parfois on trouve à la fin d'un calcul une valeur dont les dernières décimales sont inexactes, et on voudrait trouver la "vraie" valeur.
Exemple, sur la HP20S : PI / 3 = cos - 0.5 = donne 3E-12.
Cela signifie que cos(PI/3) vaut 0.500000000003 sur cette machine.
Donc si on applique sans réfléchir l'algorithme de conversion en fraction de cos(pi/3) sur HP20S, on trouvera 500000000003/1000000000000 ce qui est assez loin du résultat espéré de 1/2...
Comme d'habitude le diable est dans les détails !!
G.E. l'emm****** en chef

[C.Ret]

Oui, c'est pour cela que je trouve le MPO 97 super, connaissant laprécision de la machine, on peut optimiser l'algorithme et éviter les erreur d'arrondi ou les dépassements ::)

Mais il n'y a pas que cela en astuce.

Si sur la plupart de nos calculettes, la saisie des nombre décimaux est simple et immédiate (par exemple ). Même sur une Ti-57 LCD c'est facile (une fois le mauvais clavier réparé et les rebonds disparus !).

Mais comment fait-on, sur la même Ti-57 LCD pour saisir par exemple ou ?
Et une fois ce nombre saisi, comment fait la Ti-57 LCD pour nous donner la ou les fractions ?

[C.Ret]

Bonjour,
[...] on applique sans réfléchir l'algorithme de conversion en fraction de [...]

Et oui, c'est bien ça maintenant que l'on connait la précision de nos machines, on est obligé de faire en connaissance de cause,... et d'effets

J'aimerai bien les voir justement vos algorithmes...

Je suis un peu coincé sur ma Ti 57 LCD, comme de coutume je compte m'inspirer de vos idées pour surmonter les écueils...

[Gilles59]

La méthode que j'utilise ne sera guère utile sur une TI57 même non LCD... Sur une Prime par contre...

Deux clés:

Code : Tout sélectionner

➔Q

➔ a 'Σ(n=1,+∞,a/10^n)'

[gege]

Bonjour,
Sur Prime ce n'est pas drôle, tu tapes exact(4.23568) et elle te renvoie 26473/6250...
Je pense utiliser les fractions continues sur une machine Basic.
A+
G.E.

[dprtl]

Voici une première proposition pour TI-58C, basée sur un code Basic que j'avais écrit il y a très longtemps... et que j'avais un peu oublié. Attention, vous n'allez rien comprendre, c'est normal ; moi non plus :

Code : Tout sélectionner

000 42 STO
001 00 00
002 42 STO
003 01 01
004 59 INT
005 42 STO
006 02 02
007 01 1
008 42 STO
009 03 03
010 42 STO
011 04 04
012 43 RCL
013 00 00
014 55 /
015 01 1
016 52 EE
017 09 9
018 95 =
019 50 IXI
020 32 X/T
021 25 CLR
022 42 STO
023 05 05
024 76 LBL
025 11 A
026 43 RCL
027 00 00
028 75 -
029 43 RCL
030 02 02
031 55 /
032 43 RCL
033 03 03
034 95 =
035 50 IXI
036 22 INV
037 77 GE
038 12 B
039 43 RCL
040 01 01
041 22 INV
042 59 INT
043 35 1/X
044 42 STO
045 01 01
046 43 RCL
047 02 02
048 42 STO
049 06 06
050 43 RCL
051 01 01
052 59 INT
053 65 *
054 43 RCL
055 02 02
056 85 +
057 43 RCL
058 04 04
059 95 =
060 42 STO
061 02 02
062 43 RCL
063 06 06
064 42 STO
065 04 04
066 43 RCL
067 03 03
068 42 STO
069 06 06
070 43 RCL
071 01 01
072 59 INT
073 65 *
074 43 RCL
075 03 03
076 85 +
077 43 RCL
078 05 05
079 95 =
080 42 STO
081 03 03
082 43 RCL
083 06 06
084 42 STO
085 05 05
086 61 GTO
087 11 A
088 76 LBL
089 12 B
090 43 RCL
091 02 02
092 91 R/S
093 43 RCL
094 03 03
095 91 R/S
096 61 GTO
097 12 B

Usage, par exemple :

123.456 [RST] [R/S]

=> calcul, puis affichage du résultat :

15432 [R/S]
125

Pour les fractions périodiques, ça peut fonctionner si on fait le calcul sur la machine :

23 / 7 = [RST] [R/S]

[Gilles59]

Bonjour,
Sur Prime ce n'est pas drôle, tu tapes exact(4.23568) et elle te renvoie 26473/6250...
Je pense utiliser les fractions continues sur une machine Basic.
A+
G.E.

Oui Gege mais ça ne répond qu'à une partie du probléme.... Il y a trois autres parties :

12,35 -> 12+7/20
12,3<5> -> 556/45 et 12+16/45
12,<35> -> 1223/99 et 12+35/99
ou encore 3,<285714> qui doit donner 23/7

Je suis curieux des solutions sans CAS.

Les cas genre 12.35 sont faciles. J'avais ça au lycée sur ma 502P. Il suffit d'une boucle croissante, une multiplication puis tester si le résultat est entier. Ca marche tres bien avec les 502-602-603 et leur systeme d'arrondi genre :

Min01
2 Min00
LBL 1
MR01 x MR00 = FRAC x=0 GOTO9
ISZ GOTO 1

LBL9
MR01 x MR00 = "#/AR00"

Optimisable et pas testé mais ca doit le faire grâce au système d'arrondi va bien arranger les choses.

[C.Ret]

Voici une première proposition pour TI-58C, basée sur un code Basic que j'avais écrit il y a très longtemps... et que j'avais un peu oublié. Attention, vous n'allez rien comprendre, c'est normal ; moi non plus :

Code : Tout sélectionner

000 42 00     STO 00  021 25        CLR         043 35        1/x     064 42 04     STO 04  088 76 12     LBL B
002 42 01     STO 01  022 42 05     STO 05      044 42 01     STO 01  066 43 03     RCL 03  090 43 02     RCL 02
004 59        INT     024 76 11     LBL A       046 43 02     RCL 02  068 42 06     STO 06  092 91        R/S
005 42 02     STO 02  026 43 00     RCL 00      048 42 06     STO 06  070 43 01     RCL 01  093 43 03     RCL 03
007 01          1     028 75          -         050 43 01     RCL 01  073 65          ×     095 91        R/S
008 42 03     STO 03  029 43 02     RCL 02      052 59        INT     074 43 03     RCL 03  096 61 12     GTO B
010 42 04     STO 04  031 55          ÷         053 65          ×     076 85          +
012 43 00     RCL 00  032 43 03     RCL 03      054 43 02     RCL 02  077 43 05     RCL 05
014 55          ÷     034 95          =         056 85          +     079 95          =
015 01 52 09  1 EE 9  035 50         |x|        057 43 04     RCL 04  080 42 03     STO 03
018 95          =     036 22 77 12  x<t? GTO B  059 95          =     082 43 06     RCL 06
019 50         |x|    039 43 01     RCL 01      060 42 02     STO 02  084 42 05     STO 05
020 32         x↔t    041 22 59     FRAC        062 43 06     RCL 06  086 61 11     GTO A

Ah! Quel plaisir, enfin un MPo qui commence avec du code pour Ti classiques.

Bon effectivement ,c'est bien compliqué !
J'ai en plus bien du mal avec les codes pour TI-58/59, j'avais complètement oublié qu'ils ne sont pas mergés.
J'ai donc repris un peu le listing pour faire comme si les instructions étaient mergées comme sur une Ti-57 LCD.
Mais 7 registres et plus de 58 instructions, c'est bien trop pour ma pauvre et spartiate Ti-57 LCD

Par contre, cela m'a donné des idées. Utiliser 1/x et une décomposition inverse du type fractions continues m'inspire quelques astuces pour les nombres périodiques Comme utiliser le registre t pour la précision ultime !

Mais, c'est bien. je désespérais de voir du code Ti dans les MPO ces derniers temps
mais j'ai eut du mal à décoder . Plus l'habitude de ce style de code.

[...]Sur Prime ce n'est pas drôle, tu tapes exact(4.23568) et elle te renvoie 26473/6250...[...]

Oui pas drôle, y a même une touche dédiée qui fait ces deux conversions en une simple pression.

Mais comme dit Gilles59, le truc plus sportif va être pour les nombres périodiques ; Surtout sans le CAS

[...]Il suffit d'une boucle croissante, une multiplication puis tester si le résultat est entier. Ca marche très bien avec les 502-602-603 et leur système d'arrondi genre :

Code : Tout sélectionner

Min01  2  Min00
LBL1  MR01  ×  MR00  =  FRAC   x=0 GOTO9  ISZ GOTO1
LBL9  MR01  ×  MR00  =  "#/AR00"

Ah! Voilà du bon code qui va me servir sur ma ti-57 LCD. Je vais corriger mon programme, car l'astuce utilisée ici est bien plus courte et efficace que la méthode que j'envisageais.

Sacrée machine ces CASIO fx-602p, non seulement le code est court et efficace, mais en plus elles affichent la fraction !
Pas prêt d'afficher un fraction sur le LCD de ma Ti

P.S.: Effectivement c'est optimisable; j'initialise avec 1 comme cela on peu utiliser P0 avec des nombres entiers.

Code : Tout sélectionner

P0                                        (493)
  MAC  Min01                               002 
  LBL1  ISZ  MR01  ×  MR00  =  MinF  INT   010
         "#/ar00"  x=F HLT  GOTO1          018

Et alors 123.456 P0 affiche différents rapports et s'arrête sur l'affichage fixe " 15432/125"
Une pression sur EXE fait défiler les rapports suivant pour arriver à l'affichage fixe " 30864/250" et ainsi de suite à chaque pression sur la touche EXE ...
j'aime bien mais c'est un peu long pour les nombres dès trois chiffres. On gagne du temps avec :

Code : Tout sélectionner

P0                                        (492)
  MAC  Min01                               002 
  LBL1  ISZ  MR01  ×  MR00  =  MinF  INT   010
         x=F "#/ar00"  x=F HLT  GOTO1      019

Et alors 123.456 P0 affiche " 15432/125" et chaque pression sur EXE provoque l'affichage de la fraction réductible suivante.
ou

Code : Tout sélectionner

P0                                    (492)
  MAC  Min01                           002 
  LBL1  ISZ  MR01  ×  MR00  =  MinF    009
        FRAC  x=0 GOTO9 GOTO1          013
  LBL9  " arF / ar00 "                 019

Et alors 123.456 affiche " 15432/125" et EXE ne sert pas.

[dprtl]

Ah! Quel plaisir, enfin un MPo qui commence avec du code pour Ti classiques.

Bon effectivement ,c'est bien compliqué !
J'ai en plus bien du mal avec les codes pour TI-58/59, j'avais complètement oublié qu'ils ne sont pas mergés.
J'ai donc repris un peu le listing pour faire comme si les instructions étaient mergées comme sur une Ti-57 LCD.
Mais 7 registres et plus de 58 instructions, c'est bien trop pour ma pauvre et spartiate Ti-57 LCD

Voici ci-dessous exactement le même programme en GFA Basic. Forcément, c'est plus lisible, même si j'ai choisi les noms des variables pour simuler les registres TI :

Code : Tout sélectionner

INPUT r0
r1=r0
r2=INT(r0)
r3=1
r4=1
t=ABS(r0/1000000000)
r5=0
WHILE ABS(r0-r2/r3)>=t
  r1=1/FRAC(r1)
  r6=r2
  r2=INT(r1)*r2+r4
  r4=r6
  r6=r3
  r3=INT(r1)*r3+r5
  r5=r6
WEND
PRINT r2;"/";r3

[Gilles59]

Un peu de CAS avec la HP50g...

Comme dit Gege la commande ->Q qui transforme un réel en rationnel facilite les choses mais comme elle cherche un résultat parfait, elle ne traite pas les répétitions infinies : 0.9999999999 -> 9999999999/100000000000
Le programme ci-après donne toujours un résultat _parfaitement exact_. Il faut l'utiliser en mode 'exact' |R

Code : Tout sélectionner

« 
  0 ➔ a b f                        @ Par exemple 12.3 .035
  «
    a IP ➔Q                        @ Convertion Réel-> Rationnel  12. -> 12 
    a FP ➔Q                        @ Convertion |R -> |Q  .3  -> 3/10
    b ➔STR SIZE 1 - ➔Q            @ Longeur de la partie répétitive .035 -> 3
    DUP 1 - ALOG 'f' STO            @ Nécessaire pour la suite, ici -> 100
    ALOG b * ➔Q                    @ .035 -> 35
    DUP SIZE ➔Q                    @ Longueur du nombre, ici 2 
    ➔ d c 'Σ(n=1,∞,(d/10^(c*n)) ' @ Un peu de math pour un résultat parfait
    EXP2POW SIMPLIFY               @ Transfome les exp et log en puissance et simplifie. 
    f /                            @ Pour gérer les zéro en amont de la partie répétitive
    + SIMPLIFY +                   @ Résultat sous la forme i+j/k
    DUP SIMPLIFY                   @ Résultats sous la forme i/j
    DUP ➔NUM                       @ Résultat sour la forme xx.yyyyyyy
  »
»
'Mpo098' STO

@ Usage :
@ ------
@ 12.3 .035 Mpo098
@ Retourne sur la pile->
@ 12+601/1980
@ 24361/1980
@ 12.3353535353535

[C.Ret]

Voici ci-dessous exactement le même programme en GFA Basic. Forcément, c'est plus lisible, même si j'ai choisi les noms des variables pour simuler les registres TI :

C'est plus clair que le code pour Ti 58/58C/59 et encore un peu plus clair lorsque l'on donne aux variables des noms plus parlant

Code : Tout sélectionner

INPUT X
F=X  :   A=INT(X) : B=1  
AA=1 :  BB=0
eps= ABS(X/1E9)
 
WHILE ABS (X-A/B)>=esp
  F=1/ FRAC(F)
  S=A  :  A = AA + A*INT(F)  :  AA=S
  S=B  :  B = BB + B*INT(F)  :  BB=S
WEND
PRINT A;"/";B

Je comprends mieux l'algorithme, il s'agit bien comme je l'avais pressenti d'une décomposition à l'aide des fractions continues.
J'avais un petit programme qui utilisait cette décomposition à l'aide d'un tableau. Ici, dprtl utilise une astuce astucieuse pour construire le résultat au fur et à mesure de l'avancement.

Pour bien comprendre, prenons l'exemple de 12.35 et construisons sa fraction continue. Contrairement aux irrationnels, les nombres décimaux, fractionnaires ou rationnels ont justement un développement en fraction continue non infini.

L'idée est de considérer 12.35 comme la somme d'une partie entière et fractionnaire . Le plus logique est donc de prendre et soit .
Pour construire la décomposition en fraction continue de 12.35, on va continuer ainsi en considérant F comme la somme d'une partie entière et fractionnaire. et ainsi de suite chaque partie fractionnaire étant décomposée à son tour.

On obtient alors la décomposition suivante :

Que l'on note :


Et là, vous allez me dire tous, "Mais C.Ret, voyons c'est bien beau (et bien compliqué) mais cela ne répond pas à la question !". Et vous aurez bien raison.
Ce que l'on cherche c'est à déterminer la fraction A/B = 12.35

La méthode laborieuse que j'utilisais dans mon code pour HP-28S mémorisait la décomposition en fraction continue 12.35=[ 12; 2, 1, 6 ] et la détricoter dans l'autre sens pour obtenir la fraction :


Le code de notre ami chipoteman est plus astucieux, il calcule la fraction A/B au fur et à mesure de la décomposition. Ayant les termes A et B à chaque étape (chaque étape où l'on décompose l'inverse de la partir décimale), la précision du résultat peut être utilisée comme test d'arrêt.
Je vous laisse analyser son astuce qui consiste à chaque étape à calculer directement le numérateur A et le dénominateur B à partir des valeurs de ces deux termes à l'étape précédente et avec la valeur entière de l'inverse de la partie fractionnaire F.
Génial !
Non ?