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
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 11 juin 2014 19:23

Et c'est en testant qu'on se rend compte qu'on fait n'importe quoi !

Le positionnement du contrôle de limite est désormais incorrect et en inversant le contrôle de parité, c'est mieux et plus rapide !
Pour ULAM(77031) j'obtiens Vol : 350 Alt : 21933016 Temps : 13.92

Le code optimisé (à force, j'en doute !)

Code : Tout sélectionner

10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME
20 IF N=1 THEN 40 ELSE IF MOD(N,2)=0 THEN N=N/2 @ S=S+1 @ GOTO 20 
30 IF N>333333333332 THEN 50 ELSE N=(N*3+1)/2 @ S=S+2 @ A=MAX(A,N*2) @ GOTO 20
40 T=TIME-T @ PRINT 'Vol : ';S;' Alt : ';A;' Tps : ';T @ END
50 PRINT 'Depassement capacite'
ULAM(33554431) donne un dépassement de capacité (2^25-1)
ULAM(16777215) --> Vol : 474 Alt : 564859072960 Temps : 19.18 (2^24-1)
Dernière édition par caloubugs le 12 juin 2014 00:02, édité 1 fois.
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 : 183
Inscription : 23 mars 2014 14:11

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

Message par Céline » 11 juin 2014 19:37

Salut Caloubugs, toujours à Nevers ? :wink:
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

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 12 juin 2014 00:00

Yes, jusqu'à vendredi...
Joie !
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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2498
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 12 juin 2014 13:08

caloubugs a écrit :Le code optimisé (à force, j'en doute !)

Code : Tout sélectionner

10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME
20 IF N=1 THEN 40 ELSE IF MOD(N,2)=0 THEN N=N/2 @ S=S+1 @ GOTO 20 
30 IF N>333333333332 THEN 50 ELSE N=(N*3+1)/2 @ S=S+2 @ A=MAX(A,N*2) @ GOTO 20
40 T=TIME-T @ PRINT 'Vol : ';S;' Alt : ';A;' Tps : ';T @ END
50 PRINT 'Depassement capacite'
ULAM(33554431) donne un dépassement de capacité (2^25-1)
ULAM(16777215) --> Vol : 474 Alt : 564859072960 Temps : 19.18 (2^24-1)
Sur le HP 71B tu peux détecter le dépassement de capacité avec le flag INX qui correspond à l'exception "résultat inexact" du standard IEEE 754, par ex:

Code : Tout sélectionner

10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME @ CFLAG MATH
20 IF N=1 THEN 40 ELSE IF MOD(N,2)=0 THEN N=N/2 @ S=S+1 @ GOTO 20 
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 modifié la fin de la ligne 10 et la ligne 30.

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 12 juin 2014 17:42

zpalm a écrit : Sur le HP 71B tu peux détecter le dépassement de capacité avec le flag INX qui correspond à l'exception "résultat inexact" du standard IEEE 754, par ex:

Code : Tout sélectionner

10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME @ CFLAG MATH
20 IF N=1 THEN 40 ELSE IF MOD(N,2)=0 THEN N=N/2 @ S=S+1 @ GOTO 20 
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 modifié la fin de la ligne 10 et la ligne 30.
Merci pour l'info : c'est bien le sujet avec cette machine, un langage super performant et donc une nécessité d'avoir une vision globale des possibilités pour pouvoir en tirer le maximum (d'où le sentiment d'être en possibilité permanente d'améliorer les performances du code).

En prenant compte tes modifs (attention à la ligne 30, il faut bien A=MAX(A,N*2)) :

J'obtiens :
ULAM(77031) --> Vol : 350 Alt : 21933016 Temps : 13.83 (un chouilla mieux, mais le test est plus simple)
ULAM(33554431) donne un dépassement de capacité (2^25-1) - Ca marche effectivement au vol 48 (valeur de S lue après fin du programme) où N>5*10^11 après la division par 2.
ULAM(16777215) --> Vol : 474 Alt : 564859072960 Temps : 19.05 (2^24-1)
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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2498
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 12 juin 2014 17:50

caloubugs a écrit :En prenant compte tes modifs (attention à la ligne 30, il faut bien A=MAX(A,N*2)) :
Pas forcément, on peut déporter la multiplication par 2 à la ligne 40 pour éviter de la faire dans la boucle (ce que j'avais fait sans le dire dans mon exemple...). Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 12 juin 2014 19:19

zpalm a écrit :
caloubugs a écrit :En prenant compte tes modifs (attention à la ligne 30, il faut bien A=MAX(A,N*2)) :
Pas forcément, on peut déporter la multiplication par 2 à la ligne 40 pour éviter de la faire dans la boucle (ce que j'avais fait sans le dire dans mon exemple...). Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.
Mais oui ! Et en plus on évite 350 fois ce calcul dans la boucle !
Bien vu !

Pour moi : Vol : 350 Alt : 21933016 Temps : 13.17 (sur un Netbook qui rame... Normal).

Ça baisse, ça baisse...
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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2498
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 13 juin 2014 00:42

zpalm a écrit :Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.
caloubugs a écrit :Pour moi : Vol : 350 Alt : 21933016 Temps : 13.17 (sur un Netbook qui rame... Normal).
Sur mon HP 71B: 13.1 s , pile entre les deux émulations.

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 13 juin 2014 07:32

zpalm a écrit :
zpalm a écrit :Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.
caloubugs a écrit :Pour moi : Vol : 350 Alt : 21933016 Temps : 13.17 (sur un Netbook qui rame... Normal).
Sur mon HP 71B: 13.1 s , pile entre les deux émulations.
Impressionnant !
Je serais bien curieux de savoir comment c'est codé dans emu71 pour arriver à un tel réalisme dans l'exécution. J'imagine via des contrôles d'horloge (timers), mais faire tout passer par ça pour garantir ce réalisme, quel boulot !
Ou alors y'a une astuce...

Bravo au concepteur !
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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2498
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 13 juin 2014 09:03

caloubugs a écrit :Impressionnant !
Je serais bien curieux de savoir comment c'est codé dans emu71 pour arriver à un tel réalisme dans l'exécution. J'imagine via des contrôles d'horloge (timers), mais faire tout passer par ça pour garantir ce réalisme, quel boulot !
Ou alors y'a une astuce...
Les fichiers sources sont disponibles sur la page d’EMU71.

Dans ENGINE.C on trouve une fonction AdjustSpeed() qui est appelée après le traitement de chaque opcode :

Code : Tout sélectionner

EvalOpcode(FASTPTR(Chipset.pc)); // execute opcode
AdjustSpeed();                   // adjust emulation speed 
Pour plus de détails sur la détermination de la vitesse du HP 71B voir ICI.
caloubugs a écrit :Bravo au concepteur !
+1000 ! :D

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 13 juin 2014 23:00

Bon, je viens de faire le test sur ma 71b réelle : 12,92 s...
Fréquence du CPU : 638,48 kHz (merci pour tes infos zpalm !).

Je suis à 2 doigts de battre le record du 110 m haies :mrgreen:
En tout cas, elle carbure ma petite... Ça me rassure...
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 : 430
Inscription : 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 » 13 juin 2014 23:09

Code : Tout sélectionner

10 S=0 @ A=0 @ INPUT 'Nombre : ';N @ T=TIME @ CFLAG MATH
20 IF N=1 THEN 40 ELSE IF NOT(MOD(N,2)) THEN N=N/2 @ S=S+1 @ GOTO 20 
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 modifié la ligne 20 : if mod(n,2)=0 en if not(mod(n,2)).

Bingo !

12,37 s !
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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2498
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 14 juin 2014 01:07

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 !

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 430
Inscription : 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 » 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 !

Sur ma 71T (pour turbo :mrgreen: ) : 11,5 s
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 : 430
Inscription : 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 » 14 juin 2014 12:46

J'ai remis la main sur quelques "vieilles" notes et sur ULAM(63728127)=949, ça se faisait en 49s avec un algo pas optimisé.

Maintenant : vol=949 alt=966616035460
Temps : 32,48s !
Soit un gain de 33 %...

Ça me donne envie de reprendre les autres bécanes et de faire des tests (et ensuite de sûrement suivre une psychothérapie :roll: ).

Je vais aussi tenter de reprendre les algos en forth, rpl et assembleur.
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...

Répondre

Revenir vers « Tous les Pockets »