On pourra avoir des prix si on suit une psychothérapie de groupe.(et ensuite de sûrement suivre une psychothérapie ).
Misez p'tit Optimisez n°53 : la suite de Syracuse
Modérateur : Politburo
- Marge
- Fonctionne à 14400 bauds
- Messages : 6189
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Et encore, là c'est un code optimisé pour rechercher pour un seul nombre !caloubugs a écrit :Maintenant : vol=949 alt=966616035460
Temps : 32,48s !
Soit un gain de 33 %...
Imaginons maintenant que l'on veuille lister les temps de vol et altitudes des nombres entre 900 et 950 !
Combien de secondes ?
Modifié en dernier par C.Ret le 06 mars 2022 17:09, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Voui, c'est une première étape...C.Ret a écrit :Et encore, là c'est un code optimiser pour rechercher pour un seul nombre !caloubugs a écrit :Maintenant : vol=949 alt=966616035460
Temps : 32,48s !
Soit un gain de 33 %...
Imaginons maintenant que l'on veuille lister les temps de vol et altitudes des nombre entre 900 et 950 !
Combien de secondes ?
On peut tenter le coup pour faire une recherche sur un intervalle mais vu les temps rencontrés, oups, ça va nous mener loin .
Sauf à faire la recherche d'un nombre en langage machine.
Par exemple sur HP71B :
Partie Langage Machine
Enregistrer le source ULAMTXT par l'éditeur EDTEXT (EDTEXT ULAMTXT). Faire I pour passer en mode insertion. Attention à bien mettre 2 espaces avant les instructions et aucun avant les labels. J'ai récupéré ce code dans les LIF disponibles (il n'est pas optimisé pour la rapidité de calcul, un nouveau chantier ? ).
Code : Tout sélectionner
LEX 'ULAMLEX'
ID 153
MSG 0
POLL 0
POP1N EQU #0BD1C
RJUST EQU #12AE2
DCHXW EQU #0ECDC
HXDCW EQU #0ECB4
FLOAT EQU #1B322
FNRTN4 EQU #0F238
MFERR EQU #09393
ENTRY ULAM
CHAR #F
KEY 'ULAM'
TOKEN 1
ENDTXT
NIBHEX 811
ULAM GOSBVL =POP1N
GOC IVL
GOSBVL =RJUST
GOC IVL
C=A W
GOSBVL =DCHXW
SB=0
B=0 W
D=0 W
D=D+1 B
TEST C=A W
?C<=D W
GOYES DONE
LOOP B=B+1 W
ASRB
?SB=0
GOYES TEST
C=C+A W
GOC IVL
C=C+1 W
A=C W
B=B+1 W
SB=0
GONC LOOP (BET)
DONE C=B W
GOSBVL =HXDCW
A=C W
GOSBVL =FLOAT
C=A W
GOVLNG =FNRTN4
IVL LCHEX 0B
GOVLNG =MFERR
END
“ ULAMTXT ” ASSEMBLE
Attention à respecter l'espace avant ULAMTXT. La compilation dure environ 2 mn.
Partie BASIC :
Code : Tout sélectionner
10 INPUT "Debut intervalle :";D @ INPUT "Fin intervalle :";F @ M=0 @ T=TIME
20 FOR I=D TO F @ U=ULAM(I) @ IF U>M THEN M=U @ J=I
30 NEXT I
40 DISP "Vol Maxi : ";M;" pour N=";J;" en ";TIME-T;"s"
En 7 minutes, l'intervalle 1-10000 est balayé et le maximum est 6171 pour un vol de 261.
Bon, ici on ne contrôle pas les dépassements de capacité (mais on est tranquille jusqu'à au moins 10^8).
On ne fait pas non plus de recherche sur l'altitude maximale atteinte qui pourrait être différente du nombre pour lequel on atteint le vol max.
Sur d'autres machines, là si certains se lancent dans le LM, alors on pourrait se faire des discussions sur leur mise en oeuvre... J'ai un peu de mal avec ça, j'aimerai déjà pouvoir bidouiller un peu sur la 71.
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Un ptit code pour la HP48 en utilisant la pile au maximum :
On saisit le nombre en entrée. Retour : Alt en niveau 3, Vol en 2 et le temps en 1.
0 0 0 affichés si dépassement de la capacité.
ex : 77031 en 7,27 s.
S'il y a des spécialistes du RPL, alors là, bienvenue pour optimiser tout ça !
Code : Tout sélectionner
<< TICKS -> n t
<< 0 0 n DUP
WHILE 1 >
REPEAT DUP
IF 2 MOD
THEN 3 * 1 + 2 /
SWAP 2 + SWAP DUP
IF 5,E11 >=
THEN 3 DROPN 0 0 0 END
DUP 4 ROLL
MAX ROT ROT
ELSE 2 / SWAP 1 + SWAP
END
DUP
END
DROP SWAP 2 * SWAP
TICKS t -
B->R 81,92 / IP 100 /
>>
>>
0 0 0 affichés si dépassement de la capacité.
ex : 77031 en 7,27 s.
S'il y a des spécialistes du RPL, alors là, bienvenue pour optimiser tout ça !
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Bonsoir,
A mon humble avis, il y a trop de divisions par deux dans ce code.
On doit pouvoir obtenir quelque chose de plus efficace en ne réalisant qu'une seule division à chaque boucle :
Par ailleurs, les variables locales n et t ne sont utilisées qu'une seule fois dans le programme, je préfère utiliser la pile.
Par ailleurs, et comme le ne va pas manquer de le remarquer les lecteurs attentifs de ce forum, ce programme ne renvoit pas la valeur correcte de MAX pour les n de la forme 2^p !
Evidemment, cette version fait moins de tours de piste que celle que j'ai proposée au début de ce fil car à chaque nombre impair, elle réalise systèmatiquement la division par deux en divisant ainsi le nombre de boucles effectuées. Mais le code obtenu contient toujours des répétitions et en particulier des mouvements de pile inutiles.
Je ne suis pas sûr que cela soit réellement aussi efficace que le code suivant plus compact :
Je suis curieux d'apprendre combien de secondes met une HP-48 pour déterminer le vol de 77031 avec ces deux versions.
A mon humble avis, il y a trop de divisions par deux dans ce code.
On doit pouvoir obtenir quelque chose de plus efficace en ne réalisant qu'une seule division à chaque boucle :
Par ailleurs, les variables locales n et t ne sont utilisées qu'une seule fois dans le programme, je préfère utiliser la pile.
Par ailleurs, et comme le ne va pas manquer de le remarquer les lecteurs attentifs de ce forum, ce programme ne renvoit pas la valeur correcte de MAX pour les n de la forme 2^p !
Code : Tout sélectionner
« TICKS SWAP DUP 2 / 0 @ Initialise Ticks, TOF et MAX
WHILE ROT DUP 1 > @ Boucle jusqu'à obtenir 1
REPEAT
2 / @ calcule n/2
IF DUP FP
THEN
3 * .5 + @ n impair suivant est (3n+1)/2
ROT OVER MAX @ Remet à jour MAX
ROT 2 @ Incrémente deux fois TOF
ELSE
ROT @ ne remet pas à jour MAX
ROT 1 @ Incrémente TOF une fois seulement
END
+
END
DROP SWAP 2 * @ Laisse dans la pile TOF et MAX (corrigé x2)
TICKS 4 ROLL - B->R 81.92 / IP 100 / » @ Affiche le temps en s
Evidemment, cette version fait moins de tours de piste que celle que j'ai proposée au début de ce fil car à chaque nombre impair, elle réalise systèmatiquement la division par deux en divisant ainsi le nombre de boucles effectuées. Mais le code obtenu contient toujours des répétitions et en particulier des mouvements de pile inutiles.
Je ne suis pas sûr que cela soit réellement aussi efficace que le code suivant plus compact :
Code : Tout sélectionner
« TICKS SWAP DUP 0 @ Initialise Ticks,MAX et TOF
WHILE ROT DUP 1 > @ Boucle jusqu'à obtenir 1
REPEAT
IF 2 / DUP FP THEN 6 * 1 + END @ Calcule terme suivant de la suite
ROT OVER MAX @ Remet à jour MAX
ROT 1 + @ Incrémente TOF
END
DROP @ Laisse dans la pile MAX et TOF
TICKS 4 ROLL - B->R 81.92 / IP 100 / » @ Affiche le temps en s
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Surprise !!C.Ret a écrit :Je suis curieux d'apprendre combien de secondes met une HP-48 pour déterminer le vol de 77031 avec ces deux versions.
Le premier met 5,21 s sur une HP48G et le second 8,04 s !! Et pourquoi tant de différence ?
Il manque toutefois le contrôle de dépassement de capacité afin de s'assurer que le résultat est correct (le max ne doit pas dépasser 1.E12) à moins qu'on laisse le soin à l'utilisateur d'analyser le max affiché... Et j'ai bien l'impression que le max ne doit pas dépasser 1.E11 à cause de l'analyse du reste de la division par 2 et le 3 * qui suit... Par exemple pour 111111111111 on trouve un max à 333333333332... Et le mien (en corrigeant la ligne
Code : Tout sélectionner
<< 0 0 n DUP
Code : Tout sélectionner
<< n 2 / 0 n DUP
Bravo pour ton optimisation... Je suis encore bloqué à la pile façon HP15C ou 35S (sans avoir les OVER, ROT, N ROLL - comme dirait Johnny - etc...)
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Voici une présentation intéressante sur le sujet, par Joe Horn (septembre 2014) :
https://www.youtube.com/watch?v=d-bdTsa ... SU30gorNFw
Malheureusement, si j'ai bien tout compris en anglais, aucune preuve ne ressort de ces "motifs numériques" qu'il a trouvé ; ni aucun algorithme optimisé.
https://www.youtube.com/watch?v=d-bdTsa ... SU30gorNFw
Malheureusement, si j'ai bien tout compris en anglais, aucune preuve ne ressort de ces "motifs numériques" qu'il a trouvé ; ni aucun algorithme optimisé.
- meridian
- Fonctionne à 1200 bauds
- Messages : 1151
- Enregistré le : 29 oct. 2014 05:08
- Localisation : Seine-Saint-Denis
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Un petit déterrage, je me suis aperçu que j'avais écrit ça pour ma fx602p et oublié dans un coin...
Vu qu'il n'y a rien pour cette machine
“nb” HLT Min00 Min08
0 Min09
LBL0
1 Min0F MR00
x=F GOTO9
1 M+09 MR00 ÷ 2 =
FRAC
x=0 GOTO1
MR00 × 3 + 1 = Min00
GOTO2
LBL1
MR00 ÷ 2 = Min00
LBL2
MR08 Min0F MR00
x≥F Min08
GOTO0
LBL9
“Duree AR09 ” HLT
“Altitude AR08 ”
Vu qu'il n'y a rien pour cette machine
“nb” HLT Min00 Min08
0 Min09
LBL0
1 Min0F MR00
x=F GOTO9
1 M+09 MR00 ÷ 2 =
FRAC
x=0 GOTO1
MR00 × 3 + 1 = Min00
GOTO2
LBL1
MR00 ÷ 2 = Min00
LBL2
MR08 Min0F MR00
x≥F Min08
GOTO0
LBL9
“Duree AR09 ” HLT
“Altitude AR08 ”
- ledudu
- Fonctionne à 14400 bauds
- Messages : 5646
- Enregistré le : 26 mars 2009 13:07
- Localisation : Ile de France
- Contact :
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Machine : Casio PB-2000c
Langage : prolog
Pas de fonction Max(a,b). remplacée par (a+b+abs(a-b))/2.
Langage : prolog
Pas de fonction Max(a,b). remplacée par (a+b+abs(a-b))/2.
Code : Tout sélectionner
syra(1,N,A):-write(N),write('/'),write(A).
syra(U,N,A):-V is U/2,M is N+1,integer(V),syra(V,M,A).
syra(U,N,A):-V is 3*U+2,M is N+1,B is (A+V+abs(A-V))/2,syra(V,M,B).
?-syra(747,1,0).
47/4264
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Sympa ton implémentation de Max, simple, je n'y aurais jamais songé.ledudu a écrit :Machine : Casio PB-2000c
Langage : prolog
Pas de fonction Max(a,b). remplacée par (a+b+abs(a-b))/2.
[/code]
Sinon, ça donne quoi en perf le prolog sur PB2000 ?
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- ledudu
- Fonctionne à 14400 bauds
- Messages : 5646
- Enregistré le : 26 mars 2009 13:07
- Localisation : Ile de France
- Contact :
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Salut,
Merci, cette fonction Max, c'est un vieux souvenir, je ne sais plus d'où ça vient. Avec -ABS, ça donne le min.
Sans doute de mes débuts sur le PB-100 en 83-84. C'est assez empirique.
J'ai enlevé les piles du PB-2000c pour le ranger dans sa boite cette après midi, Arghh...
Merci, cette fonction Max, c'est un vieux souvenir, je ne sais plus d'où ça vient. Avec -ABS, ça donne le min.
Sans doute de mes débuts sur le PB-100 en 83-84. C'est assez empirique.
Code : Tout sélectionner
On peut aussi remarquer que :
abs(a-b)=max(a,b)-min(a,b) -> abs, max et min sont liés.
Et pour démontrer les formules, il suffit d'écrire :
a+b=max(a,b)+min(a,b)
Et d'ajouter ou de retrancher les deux équations.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Ayant enfin réussi à boucler mon programme en Langage Machine sur PC1500, je peux donner quelques éléments de résultats sur les performances atteintes entre BASIC et LM.
Le calcul pour ULAM(77031) met environ 0,07s en LM contre 29s en BASIC (soit un rapport d'environ 400 entre les 2 langages).
J'ai fait un programme (qui sera dans la gazette) qui permet de déterminer l'ULAM le plus élevé sur un intervalle.
Quelques ordres de grandeur :
Un programme en Python effectué sur un Core i5, va faire le calcul sur les 1.000.000 premiers nombres en 1'27" (maximum atteint pour 837799 et un vol de 524).
Le même calcul sur le PC1500A doit mettre environ 7 heures en LM (pour un total de vol d'environ 130 million).
En BASIC, ça nous amène à 4 mois environ sur la même machine.
Et sur mon HP41CV, environ 1 ans et demi....
Vive la patience !
Le calcul pour ULAM(77031) met environ 0,07s en LM contre 29s en BASIC (soit un rapport d'environ 400 entre les 2 langages).
J'ai fait un programme (qui sera dans la gazette) qui permet de déterminer l'ULAM le plus élevé sur un intervalle.
Quelques ordres de grandeur :
Un programme en Python effectué sur un Core i5, va faire le calcul sur les 1.000.000 premiers nombres en 1'27" (maximum atteint pour 837799 et un vol de 524).
Le même calcul sur le PC1500A doit mettre environ 7 heures en LM (pour un total de vol d'environ 130 million).
En BASIC, ça nous amène à 4 mois environ sur la même machine.
Et sur mon HP41CV, environ 1 ans et demi....
Vive la patience !
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
C'est bien intéressant Caloubugs toutes ces comparaisons.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
- Marge
- Fonctionne à 14400 bauds
- Messages : 6189
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Merci pour cette vidéo, dprtl, que j'avais ratée. C'est ça que j'adore avec ces machines qu'on emporte absolument où l'on veut (sauf dans la baignoire(*), la piscine et dans le vide intersidéral...), c'est bricoler de petites conjectures, laisser l'imagination vagabonder sur les nombres, rien que les nombres.dprtl a écrit :Voici une présentation intéressante sur le sujet, par Joe Horn (septembre 2014) :
https://www.youtube.com/watch?v=d-bdTsa ... SU30gorNFw
Malheureusement, si j'ai bien tout compris en anglais, aucune preuve ne ressort de ces "motifs numériques" qu'il a trouvé ; ni aucun algorithme optimisé.
Ce type a tout fait sur sa HP-67 ! c'est ce qui m'a toujours fasciné sur ces machines, en particulier celles équipées de diodes illuminant la nuit.
(*) : la baignoire, je n'en ai pas, c'est assez rare dans ma région, mais je crois que si j'en avais une, je ne m'y risquerais pas, même pour jouer à l'apprenti Archimède.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Comme je cherche à domestiquer ma toute nouvelle acquisition, je suis en train de refaire une partie de nos MPO avec celle-ci.zpalm a écrit :Le même type d’optimisation peut être appliqué sur mon programme pour HP Prime, le temps d’exécution pour N=77031 passe de 0.189s à 0.131s après optimisation, soit 30% de mieux!
A gauche la version initiale du programme; au centre la version optimisée; à droite la mesure du temps d'exécution des deux versions.
Ne maitrisant pas encore entièrement l'engin, j'ai eu l'idée de remplacer l'instruction "odd" que je ne trouvais pas par un simple FP() comme je l'avait fait sur mon HP-28S.
Par flemme, je n'ai pas définit de variable locale, mais j'utilise les variables globales définit par défaut. Ce qui a aussi pour effet de pouvoir analyser ce qui ce passe plus facilement, les résultats étant disponible hors du programme.
Code : Tout sélectionner
EXPORT MPO53(N) // Calcul de la Suite de Syracuse à partir de N
BEGIN
IP(N)▶N▶M;0▶F; // Initialise le maximum M et le compteur F (toF - temps de vol )
// IP(N) est important si l'on veut pouvoir utiliser des valeurs non entière, comme le fait le tracédes des fonctions
WHILE N>1 DO // On boucle jusqu'à arriver à 1 - la Conjecture de collaz est heureusement à chaque fois vérifiée,
1+F▶F;N/2▶N; // Incrément du Temps de Vol, Division par deux
IF FP(N) THEN // Si N est non entier, contre-carre la division et on applique la formule 3n+1:
IP(6*N+1)▶N;MAX(M,N)▶M; // Il n'y que dans ce cas que le maximum peut éventuellement évoluer (la fonction IP est facultative).
IF M>2ᴇ11 THEN KILL;END; // On en profite pour arrêter le programme si l'on a dépassé la limite. En effet à partir de 2e11 une division par deux
END; // donne un résultat entier même pour les nombres impairs, rendant la fonction FP() inapte à déterminer la parité de N
END;
RETURN {F,M}; // On retourne le temps de vol et l'altitude maximale.
END;
. .
Le gain de temps doit provenir de l'utilisation des variables globales et de la fonction FP() dont l'appel doit être plus rapide que les fonctions CAS odd ou even (entre-temps je les ai trouvées, ainsi que le catalogue de toutes les fonctions de ma machine )
Mon idée pour gagner du temps lors du parcourt de plusieurs entiers successifs (ou non d'ailleurs) était de mnémonizer des valeurs clefs.C.Ret a écrit :Imaginons maintenant que l'on veuille lister les temps de vol et altitudes des nombre entre 900 et 950 !
Combien de secondes ?
En effet, comme tous les entiers semblent nous ramener à 1, il y une grande partie des calculs qui ne servent qu'à parcourir les tronçons communs à toutes les suites de Syracuse se rapprochant justement de 1.
Ces tronçons finaux étant peu nombreux, il doit être possible de convenablement choisir les valeurs à mémoriser afin de couvrir un maximum d'arbres de suites de Syracuse en un minimum de mémoire.
Et ainsi de "court-circuiter" la fin des déterminations lorsque l'on tombe sur un tronçons déjà parcouru au cours d'un appel précèdent du code.
Pour étudier cela, j'avais construit le diagramme suivant où figure l'enchainement des Suites de Syracuse débutant à N compris entre 1 et 50.
Code : Tout sélectionner
..0:..1:..2:..3:..4:..5:..6:..7:..8:..9:.10:.11:.12:.13:.14:.15:.16:.17:.18:.19:.20:.21:.22:.23:.24:.25:.26:.27:..28:.29:..30:.31:..32:..33:..34:..35: .
1←──2←──4←──8←─16←─32←─64←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ └──21←─42←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
└───5←─10←─20←─40←─80←160←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──53←106←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──35←─70←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──23←─46←─92←184←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ │ └──61←122←244←488←976←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ │ └─325←650←1300←───←───←────←───←────←────←────←────←────← ─
│ │ │ └─433←866←1732←───←────←────←────←────←────← ─
│ │ │ └─577←1154←2308←4616←9232←────← ─
│ │ │ └... -
│ │ │ └...105.... : 47
│ │ │ └...110...: 41
│ │ │ └..112.: 27
│ │ └──15←─30←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ └──13←─26←─52←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ └──17←─34←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ └──11←─22←─44←─88←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──29←─58←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──19←─38←─76←152←304←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ │ └─101←202←────←───←────←───←────←────←────←────←────← ─
│ │ │ └───67←134←─268←───←────←────←────←────←────← ─
│ │ │ └───89←178←────←────←────←────← ─
│ │ │ └───59←─118←────←────← ─
│ │ │ └───39←────← ─
│ │ └──25←─50←100←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──33←────←───←────←───←────←────←────←────←────← ─
│ └───7←─14←─28←─56←112←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──37←─74←148←───←───←───←────←───←────←───←────←────←────←────←────← ─
│ │ └──49←───←───←────←───←────←───←────←────←────←────←────← ─
│ └───9←─18←─36←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
└───3←──6←─12←─24←─48←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─
On constate que "les branches" issues des différents N fusionnent à chaque fois sur un nombre pair particulier.
Ces "nodes" sont en fait les solutions à N == 3*K+1 avec l'antécédent K impair. En effet, si K est pair, alors le terme suivant est K/2, il n'y a pas de "bifurcation" à l'aide de 3n+1 !
Ce qui fait que ces "Nodes" sont d'excellents candidats pour un algorithme basé sur la mnémozisation.
N == 3*K+1 avec K impair revient à utiliser les N tels que N == 3*(2k+1)+1 soit N = 6k + 4
N = [ 10 16 22 28 34 40 46 52 58 64 72 78 82 88 94 100 106 112 118 ...
Tous ou presque sont visibles sur mon diagramme
Je me sert donc des listes L1 L2 et L3 pour mémoriser respectivement les valeurs des "Nodes" déjà rencontrés, leur temps de vol et leur altitude maximale.
Pour cela, la liste L0 est utilisé. En effet, je ne connaît la position d'un node qu'à la fin du calcul. C'est à dire si la suite atteind 1 ou un node déjà mémorisé.
Dans ce dernier cas, au compteur sera ajouter le temps de vol déjà connu de ce node et le maximum en cours sera comparé à celui du node.
Une fois le calcul terminé, les ondes temporairement mémorisés dans L0 seront ajoutés dans la liste L1 et les listes L2 et L3 complétées en conséquence.
Notons que comme la suite est par courue de N vers 1, en parcourant la liste temporaire L0 dans le sens inverse, on peut, pour chaque node en déduire le maximum local (variable P) à placer dans L3.
Ma calculette ne peut pas gérer de liste de plus de 10000 éléments, en cas où l'on arrive à cette limite, un élément est retiré de L1(ainsi que L2 et L3) afin de ne pas "perdre le fil". Comme il s'agit d'aller vers de grandes valeur de N, les "nodes" mnémonizées de temps de vol les plus faible sont sacrifiés les premiers.
Cette partie du code est facultative, mais elle m'a permis de comprendre et d'éviter un certain monbre d' "Insufficient Memory Error" alors que je n'utilise que quelques ko des centaines de Mo disponibles !)
Par ailleurs si quelqu'un connaît un moyen de supprimer un terme d'une suite sans utiliser DIFFERENCE, et qu'il peut nous l'expliquer, je lui en serai fort reconnaissant.
Code : Tout sélectionner
EXPORT SYR(I)
// Mnemonisation in L1 L2 L3
// Use global var L0 M N I F and P
BEGIN
//
// Test integrity of (L1,L2,L3)
// Reset (L1,L2,L3) if user press OK
//
IF SIZE(L1)<>SIZE(L2) OR SIZE(L1)<>SIZE(L3) THEN
IF MSGBOX("Unmatching L1 L2 & L3; clearing ?",1)
THEN {}▶L1▶L2▶L3;
ELSE KILL;
END;
END;
// Initiate determination
//
TICKS▶T;IP(I)▶N▶M;0▶F;{}▶L0;
PRINT;
//
// Main loop until suite converge to 1
//
WHILE N>1 DO
1+F▶F;N/2▶N;
IF FP(N) THEN
6*N+1▶N;MAX(M,N)▶M;
//
// Test whenever this "turn" is already know (in L1)
//
IF POS(L1,N)▶P THEN
//
// Already know "node" ! Update time of Flight and Maximum
//
F+L2(P)▶F;MAX(M,L3(P))▶M;
−P▶N; // Keep track of helper and BREAK
ELSE
//
// Unknow "turn" - test if it's a "node"
//
IF N MOD 6=4 THEN
//
// Check size of L1 list
//
IF SIZE(L1)≥9987 THEN
// Remove lowest altitude "node" from lists
POS(L3,MIN(L3))▶P;
PRINT(P+":"+L1(P)+"("+L3(P)+")");
−1▶L1(P);DIFFERENCE(L1,−1)▶L1;
−1▶L2(P);DIFFERENCE(L2,−1)▶L2;
−1▶L3(P);DIFFERENCE(L3,−1)▶L3;
END;
//
// Add new "node" canditade into list L0
//
CONCAT([N,F],L0)▶L0;
END;
END;
END;
END;
//
// End of main loop: 1 or an already know "node" was reach
//
IF M>2ᴇ11 THEN MSGBOX("Syracuse Over 1E12");
KILL; // Abort program if overflow has occur
END;
//
// Add new "nodes" candidates into lists (L1,L2 & L3)
//
1▶P;
WHILE SIZE(L0) DO
CONCAT(L1, L0(1,1) )▶L1; // Add node value
CONCAT(L2, F- L0(1,2) )▶L2; // Store copute ToF
CONCAT(L3,MAX(L0(1,1),P)▶P)▶L3; // Upgrade maximum
tail(L0)▶L0; // Remove node from list L0
END;
//
// End of code - return Initial N , Time of Fly , Max Altitude and execution time in s.
//
(TICKS-T)/1000▶T;
RETURN {I,F,M,T*1_(s)};
END;
La méthode est fort efficace ! La calculatrice n'a besoin que de quelques deux centaines de nodes mnémonisés pour calculer en quelques centièmes des valeurs extrêmes aux altitudes de plusieurs milliards et des temps de vols de plusieurs centaines.
. .
La première fois que l'on demande le calcul pour 7731, le code met 1.48s, mais cela sert surtout à compléter les liste avec les nouveaux "nodes".
La seconde fois, le même calcul ne prend plus que quelque millisecondes.
En effet, le node stoké dans la liste en position 169 est très vite trouvé; 3*77031+1 = 231094
On peut alors, après avoir un peu jouer avec la fonction SYR, trouver très rapidement des différentes valeurs:
. .
Evidemment les temps de calcul dépendent de ce qui a été mnémonisé dans L1.
Code : Tout sélectionner
EXPORT SYR(I)
BEGIN
IF SIZE(L1)<>SIZE(L2) OR SIZE(L1)<>SIZE(L3) THEN IF MSGBOX("Unmatching L1 L2 & L3 sizes !!! Clearing ?",1) THEN {}▶L1▶L2▶L3; ELSE KILL; END; END;
TICKS▶T;IP(I)▶N▶M;0▶F;{}▶L0;
WHILE N>1 DO
1+F▶F;N/2▶N;
IF FP(N) THEN
6*N+1▶N;MAX(M,N)▶M;
IF POS(L1,N)▶P THEN F+L2(P)▶F; MAX(M,L3(P))▶M; −P▶N;
ELSE
IF N MOD 6=4 THEN
IF SIZE(L1)≥9987 THEN POS(L3,MIN(L3))▶P; −1▶L1(P);DIFFERENCE(L1,−1)▶L1; −1▶L2(P);DIFFERENCE(L2,−1)▶L2; −1▶L3(P);DIFFERENCE(L3,−1)▶L3; END;
CONCAT([N,F],L0)▶L0;
END;
END;
END;
END;
IF M>2ᴇ11 THEN MSGBOX("Syracuse Overflow 2E11 !!"); KILL; END;
1▶P; WHILE SIZE(L0) DO CONCAT(L1,L0(1,1))▶L1; CONCAT(L2,F-L0(1,2))▶L2; CONCAT(L3,MAX(L0(1,1),P)▶P)▶L3; tail(L0)▶L0; END;
(TICKS-T)/1ᴇ3▶T;
RETURN {I,F,M,T*1_(s)};
END;
Modifié en dernier par C.Ret le 01 mars 2017 22:41, modifié 12 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.