Misez p'tit Optimisez n°53 : la suite de Syracuse

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
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

Message par Marge »

(et ensuite de sûrement suivre une psychothérapie :roll: ).
On pourra avoir des prix si on suit une psychothérapie de groupe. :lol:
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é.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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

Message par C.Ret »

caloubugs a écrit :Maintenant : vol=949 alt=966616035460
Temps : 32,48s !
Soit un gain de 33 %...
Et encore, là c'est un code optimisé pour rechercher pour un seul nombre !

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.
caloubugs
Fonctionne à 1200 bauds
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

Message par caloubugs »

C.Ret a écrit :
caloubugs a écrit :Maintenant : vol=949 alt=966616035460
Temps : 32,48s !
Soit un gain de 33 %...
Et encore, là c'est un code optimiser pour rechercher pour un seul nombre !

Imaginons maintenant que l'on veuille lister les temps de vol et altitudes des nombre entre 900 et 950 !
Combien de secondes ?
Voui, c'est une première étape...
On peut tenter le coup pour faire une recherche sur un intervalle mais vu les temps rencontrés, oups, ça va nous mener loin :twisted: .

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 ? :roll: ).

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
Ensuite quitter le mode insertion en tapant I. Passer dans l'environnement FORTH et saisir
“ 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"
Je n'ai pas utilisé la fonction max(x,y) en ligne 20 à cause de la récupération de deux valeurs U et I à mettre en M et J.

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...
caloubugs
Fonctionne à 1200 bauds
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

Message par caloubugs »

Un ptit code pour la HP48 en utilisant la pile au maximum :

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 /
    >>
>>
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 !
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...
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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

Message par C.Ret »

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 !

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
Je suis curieux d'apprendre combien de secondes met une HP-48 pour déterminer le vol de 77031 avec ces deux versions.
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.
caloubugs
Fonctionne à 1200 bauds
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

Message par caloubugs »

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.
Surprise !!
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
par

Code : Tout sélectionner

<< n 2 / 0 n DUP
pour l'erreur décelée) met 5,83 s sans ce test... (et un max correct pour 111111111111).

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 :mrgreen: - 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...
Avatar du membre
dprtl
Fonctionne à 1200 bauds
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

Message par dprtl »

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é.
Avatar du membre
meridian
Fonctionne à 1200 bauds
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

Message par meridian »

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 ”
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par ledudu »

Machine : Casio PB-2000c
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
caloubugs
Fonctionne à 1200 bauds
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

Message par caloubugs »

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]
Sympa ton implémentation de Max, simple, je n'y aurais jamais songé.

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...
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par ledudu »

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.

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.
J'ai enlevé les piles du PB-2000c pour le ranger dans sa boite cette après midi, Arghh...
caloubugs
Fonctionne à 1200 bauds
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

Message par caloubugs »

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. 8O
Et sur mon HP41CV, environ 1 ans et demi.... :slime:

Vive la patience ! :mrgreen:
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...
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

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
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
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

Message par Marge »

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é.
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.
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é.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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

Message par C.Ret »

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!
Image Image Image
A gauche la version initiale du programme; au centre la version optimisée; à droite la mesure du temps d'exécution des deux versions.
Comme je cherche à domestiquer ma toute nouvelle acquisition, je suis en train de refaire une partie de nos MPO avec celle-ci.

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;

A ma grande surprise, cela rend mon code encore bien plus rapide:
Image. .Image

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 :))
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 ?
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.
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←───←───←───←───←───←───←───←───←───←───←───←───←───←───←───←────←───←────←───←────←────←────←────←────← ─ 

Pour rendre cela plu lisible, je me suis limité aux 35 premiers niveaux des Temps De Vol. Les branches provenant 27, 41 et 47 ne sont donc pas entièrement représentées.

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.

Image. .Image

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:
Image. .Image
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.
Répondre

Retourner vers « Tous les Pockets »