Misez p'tit Optimisez n°58 : somme des cubes des chiffres

[Marge]

Match HP-19c vs HP-29c, le terrain était lourd pour ce derby très attendu, et l'état de la pelouse a pu faire un moment penser que l'arbitre arrêterait la rencontre, mais non, il n'en fut rien, et le score est sans appel :

- 0 h 44 m 34 s pour la 19 ;
- 0 h 37 m 58 s pour la 29.

La 29 est près de 15% plus rapide que la 19 (-14,81%).

[gege]

Bonjour,
Avec l'idée suggérée (plus ou moins consciemment) par C.Ret, voici un programme :

10 FOR A=0 TO 9:D=100*A-A*A*A
20 FOR B=0 TO 9:E=D+10*B-B*B*B
30 IF 0>E THEN 80
40 IF 720<E THEN 80
50 C=INT(1.1*E^.32+.5)
60 IF E+C<>C*C*C THEN 80
70 PRINT 100*A+10*B+C:IF C=1 THEN PRINT 100*A+10*B+1
80 NEXT B:NEXT A:END

Il tourne en 35 secondes sur le PB-700, soit moins de 30% du temps avant optimisation !
Le principe sera expliqué dans la prochaine Gazette
Si c'est pas de la pub ça !!
G.E.

[C.Ret]

Uh ?
A part :
10 PRINT "0 1 153 370 371 407"
je ne vois rien sous la seconde sur PC1211...
Quel est le truc ?
G.E.

C'est bien cela
1:PRINT "0 1 153 370 371 407":END

Non mais c'est de la gruge !

Sinon, ton dernier programme peut être MPO-iser
Toutes les valeurs de A et B sont parcourues, donc les 100*A et 10*B sont inutiles, il suffit d'un N=N+10 bien placé.
Ensuite les lignes 30 et 40 reviennent à faire un IF (0<E) OR (E<720). Ce qui m'a donné l'idée de simplifier mon code ; au lieu de tester 0<M et M<>INT(M), je teste ABS M<>INT M

Et l'dée du test C=1 pour afficher N+1 est excellente:

D'où ma version de ce programme pour SHARP PC-1211 qui recherche les entiers de trois chiffres :

Code : Tout sélectionner

10:FOR A=0 TO 5:FOR B=0 TO 9:M=(N-AAA-BBB)/6:IF ABS M<>INT M GOTO 30
20:D=INT (.516685+√M):IF 6M+D=DDD PRINT N+D:IF D=0 PRINT N+1
30:N=N+10:NEXT B:NEXT A:END

[/code]

[gege]

Bonjour,
Chouette mais tu 'triches' avec la limite à 5 sur A !
Je n'avais pas pensé au facteur 6...
Bien vu aussi l'incrément de N par 10.

Excellent !!
Je vais essayer sur PB-700 pour comparer.
Quel est le temps sur PC1211 ?

A tous, est-ce que je peux incorporer vos trucs dans mon article (en citant les pseudos) ?
G.E.

[Marge]

A tous, est-ce que je peux incorporer vos trucs dans mon article (en citant les pseudos) ?

Heu, pour ma part, c'est oui, mais à la condition que j'utilise l'algo le plus rapide, et en tout petits caractères.


J'édite : à la réflexion, il me semble très difficile, sinon impossible d'utiliser vos algorithmes sur les 19-29c : les boucles demandées exigent des acrobaties incroyables sur le registre 0, et l'entrée de données est très gourmande en mémoire programme. Je n'aurai de plus pas le temps de me lancer dans ce défi.

Libre à toi, gege, de publier mon programme tel quel, mais je ne pense pas qu'il soit d'un autre intérêt que celui de jouer le rôle de faire-valoir.

[zpalm]

D'où ma version de ce programme pour SHARP PC-1211 qui recherche les entiers de trois chiffres :

Code : Tout sélectionner

10:FOR A=0 TO 5:FOR B=0 TO 9:M=(N-AAA-BBB)/6:IF ABS M<>INT M GOTO 30
20:D=INT (.516685+√M):IF 6M+D=DDD PRINT N+D:IF D=0 PRINT N+1
30:N=N+10:NEXT B:NEXT A:END

Ce programme est plein d'astuces !! Mais es-tu sûr de ta formule en ligne 20 ?

Code : Tout sélectionner

20:D=INT (.516685+√M)

Je n'ai pas l'impression qu'elle donne tous les bons résultats... contrairement à celle de gege:

Code : Tout sélectionner

50 C=INT(1.1*E^.32+.5)

Et pour pinailler un peu, sur la ligne 10 on pourrait sortir AAA de la boucle FOR B.

[C.Ret]

Chouette mais tu 'triches' avec la limite à 5 sur A !
[...]
Quel est le temps sur PC1211 ?
[...]
A tous, est-ce que je peux incorporer vos trucs dans mon article (en citant les pseudos) ?
Pas de souci pour incorporer, utiliser, copier ou transformer tout ce que je met sur le forum. C'est publier pour être publique et servir à chacun.

Effectivement, je vais réflèchir à une version où A va jusqu'à 9 afin de comparer les "vitesses". Mais concernant ce point c'est plutôt les "lenteurs". Je suis comme Marge, avec mon matériel, je concours pour le programme le plus lent.

Le code ci-dessus n'a pu être testé qu'à l'instant de retour de mission, j'ai enfin pu mettre la main sur mon PC-1211 et sa CE-122).
Le programme s'arrête après environ 2 min mais il manque des valeurs. Je crois que Zalm a trouvé l'origine du problème. L'approximation de D établie sur un Commodore C128D ne semble pas fonctionner sur une vraie calculatrice.

Ce programme est plein d'astuces !! Mais es-tu sûr de ta formule en ligne 20 ?

Code : Tout sélectionner

20:D=INT (.516685+√M)

Je n'ai pas l'impression qu'elle donne tous les bons résultats... contrairement à celle de gege [... formule trop compliquée...]
Et pour pinailler un peu, sur la ligne 10 on pourrait sortir AAA de la boucle FOR B.

Effectivement, je dois corriger cela.
EDIT
Le code ci-dessous devrait mieux fonctionner

Code : Tout sélectionner

1:N=0: FOR A=0 TO 9: C=AAA: FOR B=0 TO 9: M=(N-C-BBB)/6: IF ABS M<>INT M GOTO 3
2:D=INT (2M^.32: IF 6M+D=DDD PRINT N+D:IF D=0 PRINT N+1
3:N=N+10: NEXT B:NEXT A: BEEP 1: END

Les résultats 0. (3s) 1. (4s) 153 (24s) 370.(52s) 371.(54s) 407. (60s) crépitent sur l'imprimante très rapidement (lentement ?)
Le BEEP retentit après 2min17s en testant jusqu'à A=9.

On notera que ma formule d'estimation de D n'a rien avoir, mais alors rien du tout avec les formules très compliquées de notre ami gégé.
Mais absolument rien avoir du tout du tout.[/color]

Concernant les AAA BBB et DDD j'ai même une forte envie de tous les sortir du programme.


EDIT:
L'idée est que comme on parcourt toutes les valeurs de A et B, on peut , à chaque boucle déduire la valer de N avec N <- N+10
L'idée est que C-BBB évolue aussi de la même façon entre deux valeurs successive de B . Idem pour A dont les N-AAA évoluent de façon régulière à chaque pas.


... à suivre

[gege]

Bonjour,
Attention le M de C.Ret vaut un sixième de 'mon' E, ce qui fait que sa formule est bonne pour les petites valeurs.
Au-delà de 5 ça s'écarte, mais à mon étonnement le programme de C.Ret fonctionne parfaitement, meme pour 407 (D=7) ??
Bizarre.

...et oui on peut encore optimiser !

Finalement ce MPO est moins simple que je pensais
G.E.

[zpalm]

Euh.. pour 153, INT( .516685 +√M) donne D=2 et non 3 me semble-t-il.

Sinon pour ton E, INT(E^.33 + .5) marche aussi.

[Hobiecat]

Finalement ce MPO est moins simple que je pensais

Comme souvent dans les MPOs !

[gege]

Bonjour,
Oups en effet 153 n'était pas trouvé avec la formule d'origine.
Leçon apprise aujourd'hui : dans une approximation on n'a pas besoin de beaucoup de chiffres.

Alors, qui optimise la version de C.Ret ?
Elle tourne en 27 secondes au lieu de 2 minutes 12 sur PB-700 !!
On doit encore pouvoir gratter 5 secondes ?
G.E.

[C.Ret]

Bonjour,
[...]On doit encore pouvoir gratter 5 secondes ?
G.E.

Oh! Oui facilement, car la version actuelle parcourt tous les A (de 0 à 9) et tous les B (de 0 à 9)
De la même façon que la boucle interne cherchant C a été éliminé, il doit être possible d'économiser de précieuses secondes en ne parcourant pas tous les B à chaque A !

Sans compter que l'on peut faire sans calculer le cube d'aucune valeur

[gege]

Bonjour,
Mmmm ça semble compliqué, et la consultation d'un tableau ne gagnait pas beaucoup par rapport aux cubes quand j'ai essayé, en partie parce qu'il faut remplir le tableau.
M'enfin tout est possible avec cette bande de zèbres...
G.E.

[C.Ret]

Je sais pas mais j'arrive à imprimer les résultats avec mon SHARP PC-1211 sur son CE-122 en moins de 1'18" (avec A allant jusque 9) et sans calculer aucun cube (en fait ils sont près-calculés !

Code : Tout sélectionner

1: CLEAR : F=1.5, G=2, H=.5, I=-4, J=-12.5, K=-26, L=-45.5, M=-72, N=-106.5
2: Q=1, R=4, S=10, T=20, U=35, V=56, W=84, X=120  
3: D=Z+A(5+B): IF ABS D=INT D LET C=INT 2D^.32: IF D=A(15+C) PRINT A;B;C: IF C=0 PRINT A;B;Q
4: IF D>0 IF B<9-Y LET B=B+2: GOTO 3
5: IF A<9 LET A=A+1, Z=15A+A(5+A), Y=1-Y, B=Y: GOTO 3

EDIT:
221 octets de programme - utilise pleinement les registres A à Z inclu.

Résultats et temps d'impression :

Code : Tout sélectionner

0.0.0.   4"   0.0.1.   5"   1.5.3.  11"   3.7.1.  29"   4.0.7.  31"   Fin   1'18"

Petit rappel, sur le PC-1211, les variables alphabétiques correspondent au tableau unique A() avec les correspondance A=A(1), B=A(2), C=A(3), ... Z=A(26),

Ainsi les variables A(5) à A(14) - respectivement E à N - correspondent aux sixièmes pré-calculés de 10B-B^3 dont les valeurs non nulles sont programmées à la ligne 1:
Et les variables A(15) à A(24) - respectivement de O à X - correspondent aux sixièmes pré-calculés de C-C^3

Code : Tout sélectionner

A:	centaines de N	  a		N:B(9)	(90-729)/6	-106.5		(  0-  0)/6=  0. =  0+  0.
B:	dixaines de N	  b		O:C(0)	(  0- 0)/6	   0.		(100-  1)/6= 16.5= 15+  1.5
C:	unités de N	  c		P:C(1)	(  1- 1)/6	   0.		(200-  8)/6= 32. = 30+  2.
D:	sixièmes de N-a^3-b^3		Q:C(2)	(  8- 2)/6	   1.		(300- 27)/6= 45.5= 45+   .5
E:B(0)	( 0-  0)/6	  0.		R:C(3)	( 27- 3)/6	   4.		(400- 64)/6= 56. = 60-  4.
F:B(1)	(10-  1)/6	  1.5		S:C(4)	( 64- 4)/6	  10.		(500-125)/6= 62.5= 75- 12.5
G:B(2)	(20-  8)/6	  2.		T:C(5)	(125- 5)/6	  20.		(600-216)/6= 64. = 90- 26.
H:B(3)	(30- 27)/6	   .5		U:C(6)	(216- 6)/6	  35.		(700-343)/6= 59.5=105- 45.5
I:B(4)	(40- 64)/6	- 4.		V:C(7)	(343- 7)/6	  56.		(800-512)/6= 48. =120- 72.
J:B(5)	(50-125)/6	-12.5		W:C(8)	(512- 8)/6	  84.		(900-729)/6= 28.5=135-106.5
K:B(6)	(60-216)/6	-26.		X:C(9)	(729- 9)/6	 120.
L:B(7)	(70-343)/6	-45.5		Y:  a & b pair <=0=:=1=> a & b impair
M:B(8)	(80-512)/6	-72		Z:A(a)	15*a+B(a)

Les sixièmes correspondant aux centaines ne sont pas près-calculés, ils se déduisent simplement de la valeur du sixième liée à la dizaine correspondante. En effet, on constate qu'il suffi d'ajouter 15*a au sixième de la dizaine a. (cf. Z=15*a+B(a) à la ligne 5: ) La valeur Z contient donc la valeur du sixième des centaines pour éviter de la calculer à chaque nouvelle dizaine testée.

Les variables A,B et C sont respectivement les trois chiffres de n = abc

La variable D est le sixième de la différence entre l'entier n et la somme s=a^3 + b^3 + c^3 des cubes de ses chiffres.

Petite astuce supplémentaire, pour les entiers solution, on remarque que les chiffres a et b sont toujours de même parité. Ce qui se justifie, on veut obtenir un multiple, donc une valeur entière. Or les sixièmes sont tous des entiers ou des demi-entiers. Ainsi la variable Y est utilisée pour ne tester que les chiffres B de même parité que le chiffre A.

Un gain de temps important est obtenu par rapport à la version précédente car pour chaque A, on ne parcourt que la moitié des valeurs de B (cf. B<-B+2 de la ligne 4 ).
Explication des lignes:
1: Initialisation des sixièmes pré-calculé pour les dizaines (et indirectement pour les centaines)
2: Initialisation des sixième près-calculé pour les unités
3: Boucle principale : calcul de la différence D, estimation du dernier chiffre, test et affichage de(s) entier(s)
4: Valeur suivante de B: en fonction de la parité (donnée par Y) ou passe au chiffre B suivant
5: Valeur suivante de A: incrément de A, calcul de Z, changement de parité et fin de boucle

P.S.: Même code mais pour une machine gérant les tableaux

Code : Tout sélectionner

10: CLR: DIM B(9),C%(9)
11: B(1)=1.5: B(2)=2: B(3)=.5: B(4)=-4: B(5)=-12.5: B(6)=-26: B(7)=-45.5: B(8)=-72: B(9)=-106.5
12: C%(2)=1: C%(3)=4: C%(4)=10: C%(5)=20: C%(6)=35: C%(7)=56: C%(8)=84: C%(9)=120  
13: D=Z+B(B%): IF ABS(D)=INT(D) THEN C%=2*D^.32: IF D=C%(C%) PRINT A%;B%;C%:IF C%=0 PRINT A%;B%;1
14: IF D>0 AND B%<9-Y% THEN B%=B%+2: GOTO 13
15: IF A%<9 THEN A%=A%+1: Z=15*A%+B(A%): Y%=1-Y%: B%=Y%: GOTO 13

[Marge]

"Nombres d'octets, nombres d'octets ! nous voulons des nombres d'octets !"