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

[dprtl]

Merci C.Ret pour cette analyse ! J'ai écrit ce petit programme en 1990 ; l'année où je passais le Bac. Mais je ne suis pas l'inventeur de l'algorithme. Il venait d'un vieux bouquin de programmation... que je suis incapable de retrouver aujourd'hui.

[C.Ret]

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.

En préparant cet MPO, j'ai trouvé différentes voies pour transformer un nombre en fraction. Mais je n'avait pas pensé à celle-ci.

J'étais parti plus sur une approche visant à faire disparaitre la partie fractionnaire par multiplication successive par dix.

Par exemple :


On obtient alors une fraction qu'il faut éventuellement réduire. Pour cela, les MPO où il est question de PGDC servent bien.



Avec la méthode proposée par Gilles59, on trouve plus directement le résultat :
Dans cet exemple, on trouve après avoir testé les produits de 12.35 avec les facteurs de 1 à 20.

C'est plus direct, le code peut être plus court car il n'y a pas à chercher de PGDC ni réduire la fraction résultat.
Mais dans certains cas la boucle de recherche peut prendre un certain temps !
Par exemple avec 0.5813 même avec une CASIO fx-602p cela peut prendre plusieurs minutes.

Toujours pour les cas simples comme 12.35, il y a une autre méthode pour transformer en fraction, et je suis surpris que gégé ne l'utilise pas puisque c'est lui qui nous à parler d'énumérer les rationnels !




Concernant les cas plus compliqués de nombres fractionnaires périodiques, comme , je vous invite à vous rappeler de cet MPO 74 proposé par Marge qui fait exactement l'opération inverse !

[gege]

Bonjour,
Pas si compliqué le cas des décimales périodiques.
On remarque que :
1/9 = 0.11111111111..
1/99 = 0.010101010101...
1/999 = 0.001001001001...
etc
Donc pour trouver 0.353535353535... ou .457945794579... je vous laisse deviner
G.E.

[C.Ret]

Moi, si j'étais vous, je suivrai la voie indiquée par gégé.
Sa méthode me semble mieux que de faire un truc impossible sur une Ti-57 LCD qui ne saura jamais calculer


Mais je ne suis pas vous et chacun fait comme il veut.

[bernouilli92]

Je suis étonné qu’il n’y ait pas encore une version pour hp48 utilisant la foncion ->Q.
Voici une version :

Code : Tout sélectionner

« IP LASTARG →Q
  IF DUP TYPE 0 ==
  THEN 
    SWAP DROP 0 1
  ELSE 
    OBJ→ DROP2
    DUP2 MOD ROT DROP SWAP
  END 
  3 →LIST
»

2.42857142857 Mp98 donne {2 3 7}
Et 4 Mp98 donne { 4 0 1}

[C.Ret]

Ah! Bien, en effet :


Mais, comment fait-on pour, par exemple, calculer ou ?


EDIT: Je ne résiste pas à illustrer ma réponse avec une capture d'écran réalisée depuis le dernier PockEmul créé par Remy.

MPO98 - PockEmul - CASIO Z-1 - 2._428571_.gif (43.33 Kio) Vu 5417 fois

MPO98 - PockEmul - CASIO Z-1 - 2.42_8571_.gif (43.55 Kio) Vu 5417 fois

MPO98 - PockEmul - CASIO Z-1 - 2.42857_1_.gif (42.49 Kio) Vu 5417 fois

[C.Ret]

Pas si compliqué le cas des décimales périodiques.
On remarque que :
1/9 = 0.11111111111..
1/99 = 0.010101010101...
1/999 = 0.001001001001...
etc
Donc pour trouver 0.353535353535... ou .457945794579... je vous laisse deviner

Je crois que j'utilise la même méthode, mais je n'avais pas la même approche.
Comme personne ne semble y arriver, j'étais en train de préparer une petite explication, mais j'ai trouvé un professeur de math suisse qui le fait mieux que moi, en vidéo et en français !



Et donc, en suivant cette astuce, appliquée à notre exemple de 12.(35)

d'où
et donc

[Schraf]

Bonjour à tous,

J'ai enfin réussi à faire rentrer le MPO 98 sur une Ti-57 classique (pas là LCD) mais il faut initialiser des mémoires avant de lancer le programme.

Emulateur Ti-57 ici

Je reprends l'exemple 2.42(178), on fait :

Code : Tout sélectionner

2.42 STO 0
178 STO 1 (c'est la période)
1 STO 2 (toujours)
10 STO 3 (toujours)

Et le code est le suivant :

Code : Tout sélectionner

LRN
00 33 0 	RCL 0
01 -49		INV 2nd Int	; Partie fractionnaire
02 22		x<>t		; Echange x et t
03 00		0
04 66		x = t		; On teste si RCL 0 est une valeur entière
05 51 1		GTO 1		; Si oui on continue
06 33 3		RCL 3
07 39 0		2nd Prd 0	; On multiplie RCL 0 par 10
08 39 2		2nd Prd 2	; Idem avec RCL 2
09 71		RST		; Retour au pas 00
10 86 1		Lbl 1		; On cherche maintenant le nb de chiffres de RCL 1
11 22		x<>t		; On met donc 0 dans t
12 33 1		RCL 1
13 66		x = t		; Si la période vaut 0, le dénominateur sera 1
14 51 2		GTO 2
15 18		2nd log
16 49		2nd Int
17 75		+
18 01		1
19 85		=		; ENT(log(N))+1 donne le nombre de chiffres de N
20 -18		INV 2nd log	; 10 puissance nb de chiffres
21 65		-
22 86 2		Lbl 2		; Si période vaut 0, on récupère 1 au pas suivant
23 01		1
24 85		=		; On obtient un nombre du type 99...9
25 39 0		2nd Prd 0	; On multiplie RCL 0 et RCL 2 par 99...9
26 39 2		2nd Prd 2 
27 33 1		RCL 1
28 34 0		SUM 0		; Et on ajoute RCL 1 à RCL 0
29 33 0 	RCL 0		; Recherche du PGCD entre RCL 0 et RCL 2
30 32 3		STO 3
31 33 2		RCL 2
32 32 1		STO 1		; On fait des copies des mémoires
33 86 3		Lbl 3		
34 33 3		RCL 3		; Pour trouver PGCD(a,b) :
35 65		-
36 33 2		RCL 2
37 85		=		; On cherche a - b
38 66		x = t
39 51 4		GTO 4		; Si a == b le PGCD est a
40 76		x >= t
41 32 3		STO 3		; Si a > b alors a = a - b
42 84		+/-		; b - a à l'affichage
43 76		x >= t		; Si b > a alors b = b - a
44 32 2		STO 2
45 51 3		GTO 3
46 86 4		Lbl 4
47 33 3		RCL 3		; On récupère le PGCD
48 -39 0	INV 2nd Prd 0	; qui divise RCL 0
49 -39 1	INV 2nd Prd 1	; Et RCL 1
LRN

En faisant RST puis R/S, on obtient un nombre clignotant (il me manquait un pas pour faire un R/S). Dans RCL 0 il y a 60484 et dans RCL 1 la valeur 24975.

Mettre tout le temps 1 en STO 2 et 10 en STO 3 avant de lancer un nouveau calcul :

• Avec 1 STO 0 et 3 STO 1 (c'est-à-dire 1,3333...) on obtient bien 4 et 3 dans les mémoires soit 4 / 3.

• On obtient la même chose avec 1 STO 0 et 333 STO 1 (donc toujours 1,3333...)

• Avec 1.5 STO 0 et 0 STO 1 (càd 1.5) on obtient 3 et 2 soit 3 / 2

• Et avec 4 STO 0 et 9 STO 1 (càd 4,9999...) on obtient 5 et 1 soit 5

• Environ 2 minutes 20 secondes avec l'émulateur pour retrouver 123,4(56) = 61111 / 495

• Mais avec les exemples de C.Ret, comme 2.42(8571) il faudrait attendre des heures (jours ?) avant d'avoir le résultat. C'est le calcul du PGCD qui est très lent.

[Schraf]

Pour ceux qui ne connaissent pas le langage des Ti-57, voici la traduction pour une Ti-83 Premium CE de mon post précédent :

Ti83 partie 1

Capturer 1.png (13.13 Kio) Vu 5003 fois

Ti83 partie 2

Capturer 2.png (13.07 Kio) Vu 5003 fois

Avec un exemple :

Exemple : 2.42(8571)

Capturer 3.png (7.76 Kio) Vu 5003 fois

Et pour les fractions continues, effectivement c'est un grand classique, voici un code trouvé dans le Sciences & Avenir n°36

Utile

utile.jpg (218.51 Kio) Vu 5003 fois

S&V 36

couv.jpg (119.31 Kio) Vu 5003 fois

[C.Ret]

Ah! Ah!

Ton code pour TI-57 ressemble beaucoup à ce que je suis en train de dessiner pour ma TI-57 LCD, mais en bien plus long !
En tout cas, il a la même structure et comporte les mêmes sous-parties. C'est juste l'utilisation et la façon de désigner la partie périodique qui diffère.

En tout cas, j'y ai trouvé une ou deux astuces qui pourraient bien me servir à économiser un pas ou deux et enfin pouvoir publier mon code


Sinon, l'extrait de Science et Vie est fort intéressant, on reconnait facilement du code pour SHARP PC-1211 avec ses multiplications implicites et la petite patte sur les lettres O : j'essaye tout de suite.

Code : Tout sélectionner

1:"F" AREAD G : H=G , I=INT G , B=I , E=1 , A=1 , D=0
2:IF ABS(G-B/E) <= €-9*ABS G PRINT B;"/";E : END
3:H=1/(H-I) , I=INT H , C=BI+A , A=B , B=C , C=EI+D , D=E , E=C : GOTO 2

P.S.: J'ai changé l'INPUT en quelque chose de plus pratique et remplacé les ":" par des virgules car depuis les utilisateurs de PC-1211 ont remarqué que cela est plus rapide (un tout petit peu c'est pas un foudre de guerre hein !? )

Les exemples donnés ne fonctionnent pas exactement comme indiqué: il y a une coquille dans le Science & Vie, il manque un 5;

Code : Tout sélectionner

En mode DEF
1/3*(3/4-21/5)_		[SHFT][ F ]	-23./20. 
1.71428714     		[SHFT][ F ]	171787./100209.
1.714285714     	[SHFT][ F ]	12.:7.

C'est bien compliqué, certain pocket plus performant permettent un code plus simple:

Code : Tout sélectionner

10 INPUT X @ DISP X;"= ";FRAC$(X) @ END

Et donnent des résultats similaires, mais non nécessairement identiques:

Code : Tout sélectionner

			[RUN]
1/3*(3/4-21/5)_		[END/LINE]	-1.15 = -23/20 
			[RUN]
1.71428714     		[END/LINE]	1.71428714 = 171763/100195
			[RUN]
12/7     		[END/LINE ]	1.71428571429 = 12/7

Ces codes marchent donc pour les nombres fractionnaires non périodiques, et concernant l'utilisation de la décomposition en fraction continue, il y a sur notre forum une discussion fort intéressante qui en explique l'origine et le principe. Reste à les modifier pour pouvoir y introduire des nombres fractionnaires périodiques.

En particulier 12/7 ne correspond ni à 1.714285714, ni à 1.71428571429 mais plus exactement à 1.(714285)

Et enfin, oui j'ai bel et bien été envahi par les micro-ordinateurs (Les CBM ayant été parmi les premiers à débarquer dans ma chambre !!! )

[gege]

Bonjour,
Merci messieurs !

C.Ret, ça y est on sait que tu as un HP71B, là tu vas l'user à force de tout faire avec !
Je parie que tu l'emportes pour faire tes courses...
Promener le chien...
Préparer les grillades...
Faire le plein du véhicule...
Prendre la douche (oulà !)...

On attend les programmes !
A+
G.E.

[C.Ret]

Non pas du tout ,du tout du tout, du tout , du tout,...

Je suis tout à fait capable ne pas le toucher pendant presque 10 minutes,...

Tout à fait, Monsieur, dix minutes, au moins deux fois par jour... si...si...

Il a presque le temps de s'éteindre tout seul, presque...

Et puis, Monsieur, ça ne s'use pas, c'est du matériel américain ça, Made in USA !

En plus en se moment, il m'aide aussi à rechercher une savonnette au fond de ma baignoire...
Alors, les programmes pour les nombres périodiques attendront un peu...

Sauf peut-être celui pour Ti-57 LCD, car je souhaite bien m'inspirer des travaux de Schraf pour (enfin) faire tenir mon algo dans cette p#ç^%ù~n de Ti-57 LCD au rabais.

Bon, j'aimerai utiliser trois registres, il faut tout faire en moins de 32 pas : Assembled in ITALY (pouffff...)

[Schraf]

Pour le calcul du PGCD, l'algorithme décrit dans Misez rikiki, optimisez : le PGCD est nettement plus efficace.

Avec la version ci-dessous, en faisant 123.4 STO 0, 56 STO 1 (toujours 1 STO 2, 10 STO 3), il faut également faire 0 STO 7 (ou 2nd C.t), le programme se termine en 13 secondes (au lieu de 2 minutes 20).

On trouve également en 13 secondes le résultat pour 2.42(8571) et pour 2.42857(1) (avec l'émulateur)

Code : Tout sélectionner

LRN
00 33 0 	RCL 0
01 -49		INV 2nd Int	; Partie fractionnaire
02 66		x = t		; On teste si RCL 0 est une valeur entière
03 51 1		GTO 1		; Si oui on continue
04 33 3		RCL 3
05 39 0		2nd Prd 0	; On multiplie RCL 0 par 10
06 39 2		2nd Prd 2	; Idem avec RCL 2
07 71		RST		; Retour au pas 00
08 86 1		Lbl 1		; On cherche maintenant le nb de chiffres de RCL 1
09 33 1		RCL 1
10 66		x = t		; Si la période vaut 0, le dénominateur sera 1
11 01		1		; Modification par rapport version 1 qui permet de supprimer Lbl 2
12 18		2nd log
13 49		2nd Int
14 75		+
15 01		1
16 85		=		; ENT(log(N))+1 donne le nombre de chiffres de N
17 -18		INV 2nd log	; 10 puissance nb de chiffres
18 65		-
19 01		1
20 85		=		; On obtient un nombre du type 99...9
21 39 0		2nd Prd 0	; On multiplie RCL 0 et RCL 2 par 99...9
22 39 2		2nd Prd 2 
23 33 1		RCL 1
24 34 0		SUM 0		; Et on ajoute RCL 1 à RCL 0
25 33 0 	RCL 0		; Recherche du PGCD entre RCL 0 et RCL 2 version 2
26 32 3		STO 3
27 33 2		RCL 2
28 32 1		STO 1		
29 86 3		Lbl 3		
30 33 3		RCL 3		
31 65		-
32 33 2		RCL 2
33 55		*		
34 43		(
35 38 3		2nd Exc 3	; Echange RCL 2 et 3
36 45		/
37 33 3		RCL 3		; qui est en fait le contenu de RCL 2
38 44		)		
39 49		2nd Int		
40 85		=
41 32 2		STO 2
42 -66		x != t	
43 51 3		GTO 3
44 33 3		RCL 3		; Le PGCD
45 -39 0	INV 2nd Prd 0	; qui divise RCL 0
46 -39 1	INV 2nd Prd 1	; Et RCL 1
47 33 0		RCL 0		; RCL 0
48 81		R/S		; Affichage
49 33 1		RCL 1		; RCL 1
LRN

[C.Ret]

Pour le calcul du PGCD, l'algorithme décrit dans Misez rikiki, optimisez : le PGCD est nettement plus efficace mais je n'arrive pas à le caser dans les 50 pas de la Ti-57.

J'ai le même type de souci, du coup j'utilise un calcul du PGCD encore plus rudimentaire que le tien (cf. pas 02 à 26 ) qui se contente d'une simple soustraction et de l'instruction d'échange de registre EXC 0.

Comme cette pauvre Ti-57 LCD manque cruellement de mémoire et surtout de pas de programme, l'initialisation est assez longue:
Il faut avant chaque utilisation mettre 01 dans le regsitre 0 et 1 dans le registre 2 : le nombre décimal est saisie entièrement dans le registre 1.
Par contre, le résultat est une fraction irréductible (mémorisée dans R1 et R2) Le PGCD se trouve finalement dans R0.

Il trois partie principales:

1. La première transforme le nombre fractionnaire en fraction entière simplement en multipliant numérateur et dénominateur par dix (c'est pour cela qu'il faut initialiser R0 à 1/10=0.1 car j'utilise le sous-programme LBL 3 qui divise R1 et R2 par R0.
2. La seconde altère la fraction afin d'y faire apparaitre la partie périodique. C'est là que j'ai le plus souffert. Normalement le programme n'a besoin que du nombre de chiffres périodique qui se trouvent à la fin de R1. Comme R1 est maintenant entier, c'est facile de retirer cette partie et de corriger le dénominateur dans la foulée. Mais cette &&"&'é'(_é de TI-57LCD n'a pas assez de pas de programme et ma rendu chèvre.
   Finalement je m'en sort en demandant à l'utilisateur de saisir deux paramètres les chiffres invariants et le nombre de chiffres périodiques.
3. Dans la dernière parie, qui consiste à trouver le PGCD afin de réduite la fraction, j'ai fait au plus court. Pas moyen de calculer un reste, je fais donc par soustraction, l'instruction EXC 0 me permet d'échanger à chaque boucle les deux variables.

J'e propose donc un code qui permet de déterminer la fraction irréductible d'un nombre fractionnaire qu'il soit ou non périodique.

La saisie du nombre initial se fait dans R1. R2 est tout au long du code le dénominateur (il doit donc être initialisé à 1) et R0 me sert de facteur diviseur commun correcteur. (Pour obtenir des entiers puis pour réduire la fraction).

Pour les nombre décimaux périodiques, la partie invariante et le nombre de chiffres périodiques sont renseignés lors des deux arrêts du code.

Code : Tout sélectionner

---  Fraction entière ----      --- Paramètres périodisation ----    --- Réduction résultat (PGCD) ----            
 71,01    00      RCL 1          23,01     06      LBL 1              71,01     19      RCL 1
 59       01      Frac           13        07      R/S                23,02     20      LBL 2
 26       02      x=t?           61,75,01  08      STO-1              75        21        -
 22,01    03      GTO 1          01        09        1                81,00     22      EXC 0
 28,03    04      SBR 3          75        10        -                95        23        =
 21       05      RST            13        11      R/S                50        24       |x|
                                -31        12      ALOG              -26        25      x≠t ?
                                 33        13      1/x                22,02     26      GTO 2
                                 95        14      =                  23,03     27      LBL 3
                                -26        15      x≠t ?              71,00     28      RCL 0
                                 61,65,02  16      STO×2              61,55,01  29      STO÷1
                                 71,02     17      RCL 2              61,55,02  30      STO÷2
                                 61,00     18      STO 0             -28        31      invSBR

Code : Tout sélectionner

Initialisation:          Nombre fractionnaire périodique:        Nombre fractionnaire non périodique:      Réduction du résultat:
   C.t   0,1 STO 0          Saisie "     0  "                      Saisie "     0  "                        
           1 STO 2             Saisir la partie fixe ABCD              Saisir 0 R/S ou directement R/S      Le PGCD utilise la méthode d'Euler 
ABC.CD(efgh) STO 1             puis R/S                                                                    mais par soustractions;
           RST R/S          Saisie "    1   "                      Saisie "     1  "                       Cela fonctionne mais peu être long.
                               Saisir nombre de chiffres               Saiir 0 R/S 
                               périodiques                                                               La fraction résultat irréductible est
                               Pour (efgh) saisir 4 R/S   puis  R/S                                          dans les registres 1 & 2   
Résultats:                                                                                                              
RCL 1  /  RCL 2 =                                                                          Le PGCD est affiché à la fin de l'exécution.

Quelques exemples d'utilisation :

Code : Tout sélectionner

ON/C
0.1 STO 0		12.36 STO 1		1 STO 2		RST		R/S
...		"     0  "	12  R/S
		"    1  "	2   R/S
....				9          			  (PGCD)
RCL 1  / RCL 2 =   136 / 11 = 12.36363636

Code : Tout sélectionner

ON/C
RST		0.1 STO 0		1 sto 2		12.36 STO 1		R/S
...		"     0  "	123  R/S
		"    1  "	   1  R/S
....				3      			      (PGCD)
RCL 1  / RCL 2 =   371 / 30 = 12.3666667

Code : Tout sélectionner

ON/C
RST		0.1 STO 0		1 STO 2		2.428571 STO 1		R/S
...		"     0  "	2  R/S
		"    1  "	6  R/S
....				142857     			      (PGCD)
RCL 1  / RCL 2 =   17 / 7 = 2.4285714 

Pour les nombre fractionnaires simples, lors des deux arrêt du code, on entre 0 R/S à chaque fois.:

Code : Tout sélectionner

ON/C
RST		0.1 STO 0		1 STO 2		5.25 STO 1		R/S
...		"     0  "	R/S
		"    1  "	0  R/S
....				25     			      (PGCD)
RCL 1  / RCL 2 =   21 / 4 = 5.25 

[Schraf]

Franchement, je n'aurais pas cru ça possible sur la Ti57 LCD !! C'est vrai qu'on l'aide un peu dans les étapes mais quand on voit le résultat final, ça aurait pu être un outil utilisable en classe à l'époque...

Ma version 2 tient finalement bien en 50 pas et est nettement plus rapide que la première, je vais essayer de la faire tourner en vrai sur une Ti-62 GALAXY.