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 de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 21 mai 2020 18:22

Chapeaux bas ! C'est bien un Truc comme cela que j'envisageais :) :)

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é :(
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

Avatar de l’utilisateur
Schraf
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 138
Inscription : 05 mars 2020 21:45
Contact :

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

Message par Schraf » 21 mai 2020 19:18

Oui leur serveur plante régulièrement :oops:

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 
Que l'on peut aussi écrire comme ça si on veut gagner 1 caractère (⍨ permet d'inverser les arguments)

Code : Tout sélectionner

TRANCHE←{⍵⊂⍨(⍴⍵)⍴⍺↑1}
Ça permet de réécrire DEC et PLTS:

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]]}
ou encore :

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
⌸    ∘∘    
⌸     ∘    
⌸⌸     ∘∘  
⌸⌸     ∘   
⌸⌸⌸⎕    ∘  
⌸⌸⌸⌸⌸⌸⌸⌸⎕⌺⌺
⌸⌸⌸⎕⎕⎕  ∘∘ 
⌸    ∘     
⌸  ∘ 

Avatar de l’utilisateur
Schraf
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 138
Inscription : 05 mars 2020 21:45
Contact :

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

Message par Schraf » 22 mai 2020 20:32

Version graphique LIN et LOG (Cf poste initial de @C.Ret) pour la Ti-80 (1995)

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
Et le programme principal :

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
Pour N = 703 :
IMG_20200522_232114_resized_20200522_112330324.jpg
703 partie 1
IMG_20200522_232114_resized_20200522_112330324.jpg (61.62 Kio) Consulté 6509 fois
IMG_20200522_232206_resized_20200522_112330084.jpg
703 partie 2
IMG_20200522_232206_resized_20200522_112330084.jpg (65.64 Kio) Consulté 6509 fois
Pour N=873:
IMG_20200522_223044_resized_20200522_103219548.jpg
873 partie 1
IMG_20200522_223044_resized_20200522_103219548.jpg (60.58 Kio) Consulté 6511 fois
IMG_20200522_223126_resized_20200522_103219758.jpg
873 partie 2
IMG_20200522_223126_resized_20200522_103219758.jpg (62.97 Kio) Consulté 6511 fois
A partir des Ti-82 et 83 les listes peuvent contenir 999 termes, ce qui permet de visualiser par exemple un temps de vol de 524 (avec N=837799) sur un seul écran :
ti83ce.jpg
837799 avec Vol = 524
ti83ce.jpg (133.22 Kio) Consulté 6501 fois

Avatar de l’utilisateur
Danny
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 792
Inscription : 28 déc. 2013 17:34

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

Message par Danny » 09 juil. 2020 12:09

Pas mal cette suite !
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
  >>
 >>
>>
Exemple pour 347 :
Syracuse_HP50g_1.jpg
Syracuse_HP50g_1.jpg (129.87 Kio) Consulté 6170 fois
Syracuse_HP50g_2.jpg
Syracuse_HP50g_2.jpg (136.06 Kio) Consulté 6170 fois
Casio PB-1000, fx-602P, 702P, 750P, 880p, 3600p, 3900p, 7000G, 6000G, 6500G, 6800G, 8500G, 4500P, 9900GC, 9950GB +, Graph 100+ USB, Graph 90+E, fx-CP400
HP 35, 45, 65, 21, 25, 67, 33E, 34C, 41C, 41CV, 41CX, 15C, 20S, 42S, 28S, 32S, 32SII, 200LX, 48SX, 48S, 48G, 48GX, 48G+, 49G+, 50g, 35s, 39gII, Prime
Sharp PC-1212, 1245, 1500, 1500A, 1430, 1450, 1350, 1360, 1401, 1403, 1403H, 1261, 1262, 1600, E500S, EL-9000
Canon X-07 | Psion Org. II XP, Org. II LZ 64, Series 5mx | Tandy PC-7 | Электро́ника MK-61

Avatar de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 10 juil. 2020 17:46

WOW, superbes LIN/LOG graph que tout cela, bravo !
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

Avatar de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 09 déc. 2020 22:41

caloubugs a écrit :
14 juin 2014 09:55
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.

Je passe sous la barre des 12s avec 11,66s sur mon HP 71B fonctionnant à 634,448 kHz !
Alors là, chapeau !
...
Sur ma 71T (pour turbo :mrgreen: ) : 11,5 s
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.

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
Dernière édition par C.Ret le 12 déc. 2020 19:18, édité 1 fois.
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1490
Inscription : 21 août 2016 19:04

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

Message par Ben » 12 déc. 2020 11:55

C.Ret,

Ce ne serait pas plus rapide de diviser directement N/2 et de le multiplier par 6 s'il est impair?

Ben

Avatar de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 12 déc. 2020 19:18

Effectivement ben, je suis comme toi, j'ai d'abord pensé que diviser par 2 aller accéléré les choses.
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:
caloubugs a écrit :
11 juin 2014 06:43
:mrgreen:
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
On évite alors un contrôle de parité inutile : résultat 12,07 secondes (pas rien quand même ! :? ).
Il faut faire attention également à regrouper un maximum d'instructions
Puis reprise par zpalm qui a fait remarqué que l'on ne peut pas arriver à N=1 à après un N impair.
zpalm a écrit :
11 juin 2014 12:52
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
Bien vu!

Si j’applique cette optimisation sur mon programme pour WP 34S, il suffit de remplacer la ligne

Code : Tout sélectionner

 016 BACK 008
Par:

Code : Tout sélectionner

 016 INC Y
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é).

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.
caloubugs a écrit :
14 juin 2014 09:55
zpalm a écrit :Une petite optimisation de plus avant d'aller dormir :

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'
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.

Je passe sous la barre des 12s avec 11,66s sur mon HP 71B fonctionnant à 634,448 kHz !
Alors là, chapeau !

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 !
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 !


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
En cas de dépassement, le programme est arrêté et affiche 'ERR L4:Inexact' immédiatement.

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
J'en profite pour corriger une petite erreur de recopie dans l'initialisation de M que personne n'a encore vue. Tant mieux pour ma réputation, dommage pour les internautes qui tenteraient de reproduire mes résultats.
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1424
Inscription : 27 oct. 2010 20:46

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

Message par Gilles59 » 14 déc. 2020 00:43

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 :mrgreen: ), 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×⍵}

Code : Tout sélectionner

SYR 27
111
Explications du code
  • 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
Je ne comprends rien... Ca me plait beaucoup ;D Merci Schraf !
Ca me fait penser à un passage de "Forbiden Planet"...
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49G+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+

Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1490
Inscription : 21 août 2016 19:04

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

Message par Ben » 14 déc. 2020 14:57

C.Ret a écrit :
12 déc. 2020 19:18
Effectivement ben, je suis comme toi, j'ai d'abord pensé que diviser par 2 aller accéléré les choses.
Mais, non, je n'ai pas trouvé un moyen de faire plus rapide de cette façon.
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?

Avatar de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 14 déc. 2020 21:12

Gilles59 a écrit :
14 déc. 2020 00:43
[...]Je ne comprends rien... Ca me plait beaucoup ;D Merci Schraf !
Ca me fait penser à un passage de "Forbiden Planet"...
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 :)
Ben a écrit :
14 déc. 2020 14:57
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?
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
Alors que :

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
Soit un gain de 8.85% et le plaisir de passer en-dessous de la limite spychologique des 10" !!?!??!!

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 }
Il y a 221 affectations systématiques lors du N=N/2 et 129 affectations supplémentaires pour les N impairs ce qui fait un total de 350 affectations (une par tours de roue !)

Le code avec le MOD n'utilise que 221 affectations (pour les 350 tours de roue), d'où le gain de temps ! CQFD
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1490
Inscription : 21 août 2016 19:04

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

Message par Ben » 14 déc. 2020 23:41

Ah! effectivement, ça pourrait expliquer! :-)

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.

Avatar de l’utilisateur
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2536
Inscription : 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 » 15 déc. 2020 19:19

Je ne sais pas.
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é :
MPO 53 - C128D - 77031 (2).gif
MPO 53 - C128D - 77031 (2).gif (3.09 Kio) Consulté 4922 fois
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.
SHARP PC-1211+CE-121+CE-122 | Commodore 128D+Printer P-803+SD2iec | TI-57 LCD | HP-28S+HP82240A | TI-74 BASICalc | HP-41C+2mem+stat+IR | HP-15C | SHARP PC-1360+64Ko+CE-126 | HP Prime | TI-92 II | CASIO fx-602p+FA-1 | HP-71B 64K+JPC-ROM+HPIL+card reader | Sommaire des M.P.O. | Ma...dov'il sapone !.

"All science is either physics or stamp collecting. That which is not measurable is not science." - E. R.

OlidaBel
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 37
Inscription : 04 avr. 2021 16:09

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

Message par OlidaBel » 17 avr. 2021 11:28

Céline a écrit :
26 mars 2014 19: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;
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).
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;

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6975
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

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

Message par gege » 17 avr. 2021 13:39

Bonjour,
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.

Répondre

Revenir vers « Tous les Pockets »