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

[caloubugs]

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)

[Céline]

Salut Caloubugs, toujours à Nevers ?

[caloubugs]

Yes, jusqu'à vendredi...
Joie !

[zpalm]

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]

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)

[zpalm]

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]

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

[zpalm]

Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.

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]

Sur EMU71 avec l'option "Authentic Calculator Speed" j'obtient 13.03 s pour N=77031.

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 !

[zpalm]

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.

Bravo au concepteur !

+1000 !

[caloubugs]

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
En tout cas, elle carbure ma petite... Ça me rassure...

[caloubugs]

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 !

[zpalm]

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]

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 ) : 11,5 s

[caloubugs]

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

Je vais aussi tenter de reprendre les algos en forth, rpl et assembleur.