Misez p'tit Optimisez n°53 : la suite de Syracuse
Modérateur : Politburo
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
Mon souci était que j'utilisais +\[n] pour réduire selon un rang donné la matrice issue des produits extérieurs et j'avais un souci lorsque les dimensions n'étaient pas de multiples ou sous-multiples. Je n'avais pas pensé à redimensionner la donnée de base (la série) ce qui facilite le traitement.
Mais j' n'était pas loin d'un résultat similaire tout en utilisant la série totale, le redimensionner la matrice issue du produit externe afin de regrouper (opérateur OR) ou additionner (+) en réduisant selon un des rangs afin de limiter le nombre de colonne ou de ligne. Ensuite, un petit TAU pour convertir le 'code binaire' des trois plans (barre regroupée, barre simple et point logarithmique) en code 'graphique'.
P.S.: Le serveur ne répond plus. Je posterai cela en plu clair après-demain. Localement je n'ai pas de quoi saisir les codes APL.
P.S.2: le serveur ne répond toujours pas. J'espère qu'Eric et moi n'avons pas cassé le machin qui permet de faire le Truc à gégé
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Une astuce
Code : Tout sélectionner
8⍴3↑1
1 0 0 1 0 0 1 0
TRANCHE←{((⍴⍵)⍴⍺↑1)⊂⍵}
3 TRANCHE ⍳20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 TRANCHE ⍳20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Code : Tout sélectionner
TRANCHE←{⍵⊂⍨(⍴⍵)⍴⍺↑1}
Code : Tout sélectionner
DEC←{m←⌈/⍵ ⋄ ⍺[2]×{(m⍟1⌈a),(a←2↑⍵[⍒⍵])÷m}¨(r⍴1↑⍨⌈(r←⍴⍵)÷⍺[1])⊂⍵}
PLTS←{' ⎕⌸∘⌺⌺∘⌺⌺'[+/¨1+(2↓¨w∘.≥v)+3×(⌊2↑¨w←⍺ DEC ⍵)∘.=v←0,⍳⍺[2]]}
Code : Tout sélectionner
DEC←{m←⌈/⍵ ⋄ ⍺[2]×{(m⍟1⌈a),(a←2↑⍵[⍒⍵])÷m}¨⍵⊂⍨r⍴1↑⍨⌈⍺[1]÷⍨r←⍴⍵}
Code : Tout sélectionner
6 8 PLTS SYR 2097152
⌸⌸⌸⌸⌸⎕⎕⌺⌺
⌸ ∘∘
⌸ ∘∘
⌸∘∘
⌺
10 10 PLTS SYR 27
⌸ ∘∘
⌸ ∘
⌸⌸ ∘∘
⌸⌸ ∘
⌸⌸⌸⎕ ∘
⌸⌸⌸⌸⌸⌸⌸⌸⎕⌺⌺
⌸⌸⌸⎕⎕⎕ ∘∘
⌸ ∘
⌸ ∘
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Contraintes : Listes limitées à 100 éléments, pas de "While"
Solution :
Utiliser 2 listes pour pouvoir atteindre des vols jusqu'à 200.
Goto + Lbl pour remplacer le "While"
Affichage d'un premier écran (quand le vol dépasse 100) puis d'un second
Code : Tout sélectionner
PROGRAM:SYR
1->T:X->M:1->S
CLRLIST L1,L2
LBL 1
X->L1(T
3X+1->X
IF FPART(X/2:IPART(X/6->X
T+1->T
IF X>M:X->M
IF X=1:RETURN
IF T=100
THEN
L1->L2:T-99->T
0->S:CLRLIST L1
END
GOTO 1
Code : Tout sélectionner
PROGRAM:PLTS
INPUT X
PRGM_SYR
1->XMIN
1->YMIN
M->YMAX
100(1-S)+SDIM L1->XMAX
IF S:GOTO 1
L1->L4:L2->L1
LBL 1
MLN L1/LN M->L2
FNOFF
CLRDRAW
FOR(X,1,DIM L1)
LINE(X,L2(X),X+1,L2(X))
LINE(X,0,X,L1(X))
LINE(X,L1(X),X+1,L1(X))
LINE(X+1,L1(X),X+1,0)
END
DISPGRAPH
PAUSE
IF S:RETURN
L4->L1:1->S
GOTO 1
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
J'ai fait une version pour HP 48 ou 50, pas spécialement optimisée mais surtout pour avoir un affichage graphique sympa.
Entrée: nombre de départ.
Sortie: tracé graphique linéaire et logarithmique avec affichage de l'altitude max et du temps de vol, liste des termes, temps de vol et altitude max.
Variables :
n: nombre de départ
m: terme maxi calculé (altitude maximale)
c: compteur de termes
p: coordonnées du point précédent (pour tracé des lignes)
f: temps de vol
Code : Tout sélectionner
<<
DUP 1 0 -> n m c p
<<
{ } n + // ajoute le 1er terme à la liste
"Computing..." 1 DISP
DO
IF n 2 MOD 0 == // calcule le terme suivant
THEN n 2 / 'n' STO
ELSE n 3 * 1 + 'n' STO
END
n + // ajoute le nouveau terme à la liste
c 1 + 'c' STO
IF n m > // met à jour le maximum le cas échéant
THEN n 'm' STO
END
UNTIL n 1 == // fin de la boucle quand le terme vaut 1 (fin du temps de vol)
END
ERASE // initialise la zone graphique
1 c XRNG // abscisse de 1 jusqu'au nombre de termes (= temps de vol)
1 m YRNG // ordonnée de 1 jusqu'au terme maxi (= altitude maxi)
CLLCD
"Drawing..." 1 DISP
(0,0) 'p' STO
1 c FOR i // parcourt la liste pour tracer le graphique
DUP
i GET
i SWAP
R->C DUP // R->C transforme X et Y en un seul objet complexe (X,Y)
p
LINE // trace la ligne entre le point en cours et le précédent
'p' STO // stocke les coordonnées pour tracer la ligne suivante
i GET LN
m LN / m *
i SWAP
R->C PIXON // trace le terme en coordonnées logarithmiques
NEXT
PICT 1 m R->C m ->STR 1 ->GROB GOR // affiche l'altitude max sur le graphique
DUP SIZE 1 - -> f
<<
PICT f .9 * m R->C f ->STR 1 ->GROB GOR // affiche le temps de vol sur le graphique
PICT RCL ->LCD { } PVIEW // affiche le graphique final
f "flight time" ->TAG // affiche le temps de vol et l'altitude max dans la pile
m "max. altitude" ->TAG
>>
>>
>>
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
Ayant depuis peu un nouvel engin à ma disposition, j'ai relu avec intérêt cette partie de la discussion afin de reproduire les codes pour HP-71B et d'en apprendre le fonctionnement.caloubugs a écrit : ↑14 juin 2014 09:55Alors là, chapeau !zpalm a écrit :Une petite optimisation de plus avant d'aller dormir :J'ai ajouté la ligne 15 et modifié la ligne 20 : inutile de tester si N=1 après la ligne 30 car (N*3+1)/2 est > N.Code : Tout sélectionner
...
Je passe sous la barre des 12s avec 11,66s sur mon HP 71B fonctionnant à 634,448 kHz !
...
Sur ma 71T (pour turbo ) : 11,5 s
J'ai donc suivit pas à pas l'évolution de l'algorithme et tenu compte des remarques et observation formulée par caloubugs et zpalm. Et comme eux, j'ai vu mon HP-71B aller de plus en plus vite pour trouver temps de vol et altitudes maximales.
Je me suis inspiré de leurs code pour produire un code plus court et plus efficace en ajoutant une astuce supplémentaire qui vient s'ajouter aux astuces déjà exploité par mes confrère et fait gagner quelque cycle :
L'idée est de ne pas mettre à jour l'altitude maxime ni faire le test de dépassement systématiquement.
On sait que l'altitude maximale ne croit que lorsque N est impair.
Tous les codes pour HP-71B publiés jusqu'ici mettent à jour l'altitude maximale lorsque N est impair en utilisant l'instruction M=MAX(M,N).
Mon idée était de tenter de gagner un peu de temps en effectuant la mise à jour de M après un test afin de ne pas exécuter systématiquement l'affectation avec la fonction MAX. J'utilise donc un code du type IF M<N THEN M=N
Le gain serait resté minime si je n'avais pas eu l'idée de ne plus faire le test de dépassement sauf lorsque que je mets à jour le registre M.
Après avoir un peu bataillé avec les contraintes imposées par le vérificateur de syntaxe du HP-71B, j'ai trouvé un moyen de faire une sorte de IF M<N THEN M=N @ IF M>Lim THEN DISP ("Dépassement")
Tenant compte de la suggestion de zpalm et après avoir étudié le fonctionnement des exceptions mathématiques gérées sur l'HP-71B, j'en suis arrivé à passer sous la barre des 10 secondes pour 77031 et moins de 15 seconde pour 16777251 :
Code : Tout sélectionner
CAT MPO53 BASIC 167 12/08/20 21:25
1 INPUT "Syracuse ";N @ T=TIME @ S=0 @ M=N @ CFLAG INX
2 IF N=1 THEN DISP S;2*M;TIME-T @ END
3 IF NOT MOD(N,2) THEN N=N DIV 2 @ S=S+1 @ GOTO 1
4 N=(3*N+1) DIV 2 @ S=S+2 @ IF M>N THEN 3 ELSE M=N @ IF FLAG(INX) THEN DISP "Overflow" ELSE 3
RUN Syracuse 27 111 9232 3.17"
Syracuse 8388609 168 25165828 4.8"
Syracuse 77031 350 21933016 9.67"
Syracuse 8388607 473 188286357652 13.34
Syracuse 16777215 474 564859072960 14.55"
Syracuse 837799 524 2974984576 15.83"
Syracuse 33554431 Overflow
Décidément ce fil aura été le lieu de mon entrainement sur plusieurs machines HP Prime, fx-602p, TI-92 II et HP-71B.
Ainsi qu'un des premiers code en assembleur pour mon Commodore C128D...
WOW
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Ce ne serait pas plus rapide de diviser directement N/2 et de le multiplier par 6 s'il est impair?
Ben
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
Mais, non, je n'ai pas trouvé un moyen de faire plus rapide de cette façon.
C'est justement une des astuces pour aller plus vite qui avait été notée par caloubugs:
Puis reprise par zpalm qui a fait remarqué que l'on ne peut pas arriver à N=1 à après un N impair.caloubugs a écrit : ↑11 juin 2014 06:43
Or, quand on multiplie par 3n et qu'on ajoute 1, on arrive toujours sur un nombre pair (puisqu'on part alors d'un nombre impair), du coup je modifie la ligne 20 en :On évite alors un contrôle de parité inutile : résultat 12,07 secondes (pas rien quand même ! ).Code : Tout sélectionner
20 s=s+1 @ if mod(n,2)=0 then n=n/2 else n=(n*3+1)/2 @ s=s+1
Il faut faire attention également à regrouper un maximum d'instructions
L'idée est que comme l'on sait que 3*N+1 est pair, on évite d'aller faire le test de parité; on évite ainsi des opérations (n'oublions pas que ce BASIC est interprété, pas compilé).zpalm a écrit : ↑11 juin 2014 12:52Bien vu!caloubugs a écrit : Or, quand on multiplie par 3n et qu'on ajoute 1, on arrive toujours sur un nombre pair (puisqu'on part alors d'un nombre impair), du coup je modifie la ligne 20 en :Code : Tout sélectionner
20 s=s+1 @ if mod(n,2)=0 then n=n/2 else n=(n*3+1)/2 @ s=s+1
Si j’applique cette optimisation sur mon programme pour WP 34S, il suffit de remplacer la lignePar:Code : Tout sélectionner
016 BACK 008
Code : Tout sélectionner
016 INC Y
J'ai de plus regroupé les deux incrémentations de S en une seule (ce qui va plus vite), d'où mon S=S+2 de la ligne 4. C'est cela qui fait gagner des cycles, on avance de deux case dans le jeu de l'énumération des valeurs de la suite de Syracuse.
La remarque de zpalm m'incite à boucler vers la ligne 3 ce qui évite pas mal de tests inutiles vérifiant que N vaut 1. par contre, la ligne n° 3 doit boucler sur la ligne n°2 après avoir traité un nombre N pair sinon pas de test de fin !caloubugs a écrit : ↑14 juin 2014 09:55Alors là, chapeau !zpalm a écrit :Une petite optimisation de plus avant d'aller dormir :J'ai ajouté la ligne 15 et modifié la ligne 20 : inutile de tester si N=1 après la ligne 30 car (N*3+1)/2 est > N.Code : Tout sélectionner
10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME @ CFLAG MATH 15 IF N=1 THEN 40 20 IF NOT MOD(N,2) THEN N=N/2 @ S=S+1 @ GOTO 15 30 N=(N*3+1)/2 @ S=S+2 @ A=MAX(A,N) @ IF FLAG(INX) THEN 50 ELSE 20 40 T=TIME-T @ PRINT 'Vol : ';S;' Alt : ';A*2;' Tps : ';T @ END 50 PRINT 'Depassement capacite'
Je passe sous la barre des 12s avec 11,66s sur mon HP 71B fonctionnant à 634,448 kHz !
Comme quoi, faire de l'algorithmique sur papier même si le programme parait simple peut faire gagner beaucoup de temps !
Il fallait organiser le code en fonction des variations de parité de n ET sa position par rapport à 1.
T'as mis la barre très haut !
EDIT: 2020-DEC-13
En cherchant à modifier mon code selon la remarque de ben, je n'ai pas trouvé le moyen de faire mieux en déplaçant la division par 2.
Par contre en relisant le Manuel d'Utilisation, j'ai découvert que sur les HP-71B, il n'est pas nécessaire de tester le dépassement de capacité; le pocket le fait tout seul pour nous, il suffit de lui le demander très simplement à l'aide d'une instruction TRAP.
J'ai donc modifié mon code et nous n'avons plus à tester le dépassement de capacité pour arrêter le calcul de la Suite de Syracuse; c'est le dépassement de capacité qui arrête notre calcul immédiatement:
Code : Tout sélectionner
CAT
MPO53 S BASIC 158 12/13/20 01:15
LIST
1 DESTROY ALL @ INPUT "Syracuse ";N @ T=TIME @ M=N/2 @ CFLAG INX @ S=0*TRAP(INX,0)
2 IF N=1 THEN DISP S;2*M;TIME-T @ END
3 IF NOT MOD(N,2) THEN N=N/2 @ S=S+1 @ GOTO 2
4 N=(3*N+1)/2 @ S=S+2 @ IF M>N THEN 3 ELSE M=N @ GOTO 3
Bon, tel que je l'ai programmé, l'effet de la trappe reste actif même après l'exécution du code cela laisse votre HP-71Bdansun état de paranoïa avancé où il préfère arrêter immédiatement toute opération plutôt que de risquer de vous présenter ou de conserver la moindre approximation. Il vous sera donc impossible d'extraire la moindre racine carrée ou une quelconque des fonctions trigonométriques ou transcendantales.
Votre pocket reprendra ses esprits et vous cachera quelques imperfections dès que vous aurez remis de l'ordre dans le traitement des exceptions mathématiques par une commande DEFAUT avec vos paramètres habituels ou une commande RESET qui remettra de l'ordre original dans les drapeaux (utilisateur et système), les exceptions et trappes.
J'aurais pû aussi, car ce n'est pas un MPO, faire un bout de code en plus et remettre en ordre à la fin du programme :
Code : Tout sélectionner
CAT
MRA1st BASIC 166 12/13/20 09:05
LIST
1 DESTROY ALL @ CFLAG INX @ I=TRAP(INX,0) @ INPUT "Syracuse ";N @ T=TIME @ M=N/2
2 IF N=1 THEN DISP S;2*M;TIME-T @ I=TRAP(INX,I) @ END
3 IF NOT MOD(N,2) THEN N=N/2 @ S=S+1 @ GOTO 2
4 N=(3*N+1)/2 @ S=S+2 @ IF M>N THEN 3 ELSE M=N @ GOTO 3
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Je ne comprends rien... Ca me plait beaucoup ;D Merci Schraf !Schraf a écrit : ↑14 mai 2020 18:27 Bonjour tout le monde !
Bon, comme j'étais plongé dans l'APL depuis quelques semaines (ça a du bon le confinement ), je vous livre une version (piquée sur un site) de la suite de Syracuse dans ce langage :
Code : Tout sélectionner
SYR← {1=⍵:0 ⋄ 1+∇⊃⍵⌽0 1+0.5 3×⍵}
Explications du codeCode : Tout sélectionner
SYR 27 111
- Si 1=⍵ renvoyer 0
- Sinon faire 1+ SYR(prochain_nombre) (∇ pour l'appel récursif avec comme paramètre tout ce qui est droite)
- Calcul du prochain nombre : 0.5 3×⍵ donne la liste [0.5⍵ , 3⍵], on y ajoute la liste [0 ,1] ce qui fait [0.5⍵, 3⍵+1]
- Ensuite l'astuce est de faire tourner ⍵⌽ cette liste ⍵ fois, donc si ⍵ est pair la liste ne bouge pas sinon le 3⍵+1 se retrouve en 1ere position
- On prend le premier élément ⊃ de la liste
- Conclusion, si ⍵ est pair on récupère bien 0.5⍵ sinon 3⍵+1
Ca me fait penser à un passage de "Forbiden Planet"...
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
C'est parce que vous utilisez le MOD(n,2). La fonction n'est pas disponible en Basic Sharp. Le MOD prend moins de temps d’exécution qu'une division?
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
Oui, l'APL est vraiment un truc à essayer, les RPL à coté c'est de la rigolade.
Et les site indiqué par Schraf sont très bien fait et d'excellents terrain de découverte
Oui, j'ai aussi beaucoup de mal. tous mes codes (HP-28S, SHARP PC, HP-41C,...) les plus rapides divisent tous par deux au début de chaque tour de roue et traitent en fonction du fait que l'on obtient un entier ou non.
Si j'applique la même logique avec le HP-71B, j'ai avec la fonction FP quelque chose de plus lent que la version avec les MOD(N,2).
Code : Tout sélectionner
1 DESTROY ALL @ I=TRAP(INX,0) @ INPUT "Syracuse ";N @ T=TIME @ M=N/2
2 IF N=1 THEN DISP S;2*M;TIME-T @ I=TRAP(INX,I) @ END
3 N=N/2 @ IF NOT FP(N) THEN S=S+1 @ GOTO 2
4 N=.5+3*N @ S=S+2 @ IF N<M THEN 3 ELSE M=N @ GOTO 3
RUN
Syracuse 77031
350 21933016 10.45
Code : Tout sélectionner
1 DESTROY ALL @ I=TRAP(INX,0) @ INPUT "Syracuse ";N @ T=TIME @ M=N/2
2 IF N=1 THEN DISP S;2*M;TIME-T @ I=TRAP(INX,I) @ END
3 IF NOT MOD(N,2) THEN N=N/2 @ S=S+1 @ GOTO 2
4 N=.5+1.5*N @ S=S+2 @ IF N<M THEN 3 ELSE M=N @ GOTO 3
RUN
Syracuse 77031
350 21933016 9.6
Je suis comme toi ben, j'y perds mon latin.
Y aurait-il une actuce dans cette fonction MOD pour qu'elle soit plus rapide qu'une division et extraction de la partie décimale ??
EDIT:
Je viens de comprendre; pour expliquer j'ai 'profilé' mon code pour le cas N=77031 entre accolades le nombre de fois que chaque tronçon est exécuté:
Code : Tout sélectionner
1 { x1 DESTROY ALL @ I=TRAP(INX,0) @ INPUT "Syracuse ";N @ T=TIME @ M=N/2 }
2 { x93 IF N=1 } THEN { x1 DISP S;2*M;TIME-T @ I=TRAP(INX,I) @ END }
3 { x221 IF NOT MOD(N,2) } THEN { x92 N=N/2 @ S=S+1 @ GOTO 2 }
4 { x129 N=.5+1.5*N @ S=S+2 @ IF N<M } THEN { x115 GOTO 3 } ELSE { x14 M=N @ GOTO 3 }
Est plus rapide car il n'y a que 221 affectations N=... du registre N (exactement 92 quand N est pair et 129 quand N est impair)
Le code utilisant la division par deux et le test FP revient presque au même - en fait évaluer NOT MOD(N,2) n'est pas beaucoup plus lent qu'évaluer NOT FP(N) - mais , car il y a visiblement un MAIS :
Mais, le nombre d'affectation N=... et d'évaluation d'expression est bien plus grand car l'absence de traitement sur les N pairs ne vient pas compenser l'effort supplémentaire occasionner par la division systématique (il y a plus de N impairs que pairs !).
Code : Tout sélectionner
1 {x1 DESTROY ALL @ I=TRAP(INX,0) @ INPUT "Syracuse ";N @ T=TIME @ M=N/2 }
2 { x93 IF N=1 } THEN { x1 DISP S;2*M;TIME-T @ I=TRAP(INX,I) @ END }
3 { x221 N=N/2 @ IF NOT FP(N) } THEN { x92 S=S+1 @ GOTO 2 }
4 { x129 N=.5+3*N @ S=S+2 @ IF N<M } THEN { x115 GOTO 3 } ELSE { x14 M=N @ GOTO 3 }
Le code avec le MOD n'utilise que 221 affectations (pour les 350 tours de roue), d'où le gain de temps ! CQFD
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Est-ce que ça aiderait de faire le N=N+.5 plutôt que la division? Sur Commodore, ça n'aide pas, on perd 0,2 sec.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- 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
Ce qui est sûr c'est que la version la plus rapide dépend beaucoup des systèmes, par exemple sur un Commodore C128D, la version avec la division systématique est la plus rapide. A moins de trouver une test équivalent à N MOD 2 efficace car, avec la version ci-dessous, l'économie du nombre moindre d'affectations et calculs pour N ne suffit pas à compenser le surcoût engendré :
Notons qu'il manque dans ces codes le test de dépassement de capacité; il n'y a pas sur les CBM de gestion des exceptions mathématiques.
-
- Fonctionne à 300 bauds
- Messages : 108
- Enregistré le : 04 avr. 2021 16:09
- Localisation : 50.693165,4.573478
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
J'obtiens pas le même résultat avec ce programme proposé (oui je réponds à un message vieux de 7 ans). Sur la 48GX je monte à 966,616,035,460 en 950 étapes pour un départ à 63,728,127 (vu sur "Collatz Conjecture in Color - Numberphile "https://www.youtube.com/watch?v=LqKpkdR ... umberphile à 02':09).Céline a écrit : ↑26 mars 2014 18:38 Une proposition non optimisée pour la hp-prime, histoire de l'utiliser un peu cette machine…Code : Tout sélectionner
export syracuse(n) begin local c=0, m=0; repeat c:=c+1; m:=max(m,n); if fp(n/2)==0 then n:=n/2 else n:=3*n+1 end; until n==1; {c+1,m}; end;
La Prime me donne : 283 étapes et hauteur 536,403,228,640 . Un truc m'échappe. Disclaimer en majuscules : c'est mon premier 'run' sur la Prime.
C'est bon j'ai trouvé, c'est la division par 2 qui coince, les nombres sont trop grands, tronqués sans doute...?. J'ai remplacé par le Modulo 2 et c'est OK.
Qui comprend cette limite ?
export syracuse(n)
begin
local c=0, m=0;
repeat
c:=c+1;
m:=max(m,n);
if n MOD 2 ==0
then n:=n/2
else n:=3*n+1
end;
until n==1;
{c+1,m};
end;
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
De façon générale tout ce qui travaille sur des nombres entiers potentiellement grands devrait être programmé comme des fonctions "CAS".
Il me semble que les calculs sont alors exacts jusqu'à 1500 chiffres.
A tester
G.E.