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

[cgh]

En attendant j'ai fais tourner le basic-cgh sur mon Panasonic HHC de 1983 qui trouve fièrement les 6 valeurs en 12s et balaye les 1000 en 16,5s ... pas mal le papi-pocket !

As-tu essaye avec des variables entieres ? Il y a une syntaxe pour n'utiliser que des variables entieres en utilisant % apres le nom. Ainsi U devient U%. Avec mon algo, nous avons que des entiers compris entre 1000 et 9^3*3 soit 2187 donc dans la plage entiere des -32768..32767. Je pense qu'avec les variables entieres, on devrait aller un peu plus vite...

Code : Tout sélectionner

10 FOR C%=0 TO 9
20 FOR D%=0 TO 9
30 FOR U%=0 TO 9
40 T%=C%*100+D%*10+U%
50 Z%=C%*C%*C%+D%*D%*D%+U%*U%*U%
60 IF T%=Z% THEN PRINT "Nombre: ";T
70 NEXT U%
80 NEXT D%
90 NEXT C%

Toutes les machines a base de MS Basic ont des variables entieres HHC+MS BASIC, X-07,...

[C.Ret]

Chouette un MPO, cela faisait trop longtemps.

Comme je travaillais hier, j'ai pris un peu de retard. L'avantage est que je vais pouvoir m'inspirer de vos productions. Et comme il faut que quelques secondes à certaines machines pour afficher les résultats, je vais tenter de le faire en moins de 13 min sur mon pauvre et vieux matériel !

L'idée d'imbriquer trois ou quatre boucles me plait bien.
Mais par contre, il faut alors faire attention à ne pas refaire sans cesse les mêmes calculs, surtout dans la boucle principale.

Outre le fait que les valeurs p=i^3 peuvent être pré-calculées pour les nombre de 0 à 9 (surtout sur certaines machines lentes qui estime les puissances entière avec une expression du type p=exp(3.ln(i)) ou je ne sais quoi de transcendant.

Il y a aussi à tenir compte que pour un nombre N à, 4 chiffres a b c et d, calculer N=1000*a+100*b+10*c+d et S=a^3+b^3+c^3+d^3 revient à faire bien trop de calculs inutiles.

En effet, dans la boucle la plus interne parcourant par exemple d, les expressions 1000*a+100*b+10*c et a^3+b^3+c^3 sont en réalité des constantes.

Ensuite le test d'affichage d'un résultat valable revient à comparer deux sommes dont les termes sont positifs et parcourus de façon croissante. Il s'agit donc de comparer deux fonctions croissantes.
Il doit donc y avoir le moyen de simplifier le test (tout au moins de faire en sorte qu'il nécessite moins de calculs)
Utiliser les taux d'accroissement plutôt que les valeurs absolues.
Et surtout de ne pas parcourir toutes les quatre boucles imbriquées quand les taux d'accroissement (l'un est linéaire et l'autre cubique) vont rendre vaine toutes chances d'aboutir ;
Par exemple rien ne sert de tenter de trouver une solution pour a=4. En effet avec a=4, les entiers N sont dans l'intervalle [ 4000 5000 [ et les cubes des trois autres chiffres ne pourront totaliser plus de 3*9^3 = 729 c'est à dire que les valeurs S seront comprises dans l'intervalle [ 64 793 ].
Donc rien ne sert d'aller au-delà de a=3

Afin la boucle parcourant le dernier chiffre, est-elle bien nécessaire ?
Ne peut-on pas trouver la ou les valeurs de d qui conviennent à partir des valeurs N et S déduite du parcourt de la boucle du chiffre c ?
Car pour a,b et c fixés, le chiffre d doit être solution de l'équation N + d == S + d^3 où N et S sont les valeurs pour abc0
Ce qui revient à N-S == d.(d^2 - 1)
Les valeurs prises par d.(d^2 - 1) pour d variant de 0 à 9 sont 0, 0, 6, 24, 60, 120, 210, 336, 504 et 720
Donc, si N-S==0 lorsque l'on choisi le chiffre c, alors on sait que seront solutions les nombres abc0 et abc1 obtenus avec d=0 et d=1.
Sinon, rien sert de chercher un potentiel dernier chiffre si lorsque l'on a choisi le chiffre c, la différence N-S n'est pas un multiple de 6.


Vous l'aurez compris, je me réveille et je suis en pleine cogitation MPOesque

[bernouilli92]

Voici une version RPL :

Code : Tout sélectionner

<<
  { } 
  0 9 FOR I
    0 9 FOR J
      0 9 FOR K 
        I 100 * J 10 * + K +
        I 3 ^ J 3 ^ + K 3 ^ +
        IF OVER == THEN + ELSE DROP END
      NEXT
    NEXT
  NEXT
>>

[gege]

Hello
1 min 30 sur ma fx-8500G avec le code suivant (qui peut peut-être être optimisé en utilisant la fonction Isz, j'ai pas testé)[/code]

Sympa et original ce style !
Il manque quand même l'initialisation de C, D et U pour pouvoir lancer le programme.
Bizarre C D U ? On s'attendait à C D E ou autre A B C / X Y Z...
La 8500 est "rapide" comparée à mon pauvre PB-700...

@C.Ret : tu me donnes des idées !!!

G.E.

[bernouilli92]

Bizarre C D U ? On s'attendait à C D E ou autre A B C / X Y Z...

Comme Centaine Dizaine Unité.

En tenant compte de certaines remarques de C.Ret, voici une seconde version en RPL :

Code : Tout sélectionner

<<
  { } 
  0 9 FOR I
    I 100 * I 3 ^ -> A B <<
    0 9 FOR J
      A J 10 * + B J 3 ^ + -> A B <<
      0 9 FOR K 
        A K +
        B K 3 ^ +
        IF OVER == THEN + ELSE DROP END
      NEXT >>
    NEXT >>
  NEXT
>>

Je n'ai pas pu la tester sur une vraie hp48, par contre en émulation "authentic speed", la première version tourne en 81 secondes, la seconde version est deux fois plus rapide avec un temps d'exécution de 40,5 secondes.

[Keeper]

Hello
1 min 30 sur ma fx-8500G avec le code suivant (qui peut peut-être être optimisé en utilisant la fonction Isz, j'ai pas testé)[/code]

Sympa et original ce style !
Il manque quand même l'initialisation de C, D et U pour pouvoir lancer le programme.
Bizarre C D U ? On s'attendait à C D E ou autre A B C / X Y Z...
La 8500 est "rapide" comparée à mon pauvre PB-700...

Oui C D U comme Centaines Dizaines et Unités.
J'initialise les variables à 0 avec Mcl au lieu de faire 0->C, 0->D et 0->U

[Marge]

J'en suis à la mise au point d'un pgm pour HP-19c sans algorithme particulier - donc, pas très intelligent ni très vif. Le temps d'attente d'un quelconque résultat est très long ! Mais bon, c'est dimanche.

[C.Ret]

Ben c'est comme réaliser ce type de programme sur un SHARP PC-1211
Il faut pas être pressé.

Ma machine la plus véloce met 12.3s pour tester tous les entiers entre 0 et 3000.
Le même engin met 10.7s pour tester jusqu'à seulement 900.
Le dernier des entiers qui égale à la somme des cubes de ses chiffres, est trouvé dans les deux cas au bout de seulement 4.7s

Code : Tout sélectionner

10 DIM n%(4),d%(4),p%(9):FOR i=1 TO 9:p%(i)=i^3:NEXT:e%=1000:i=3:   REM *** Initialisation et pré-calcul des cubes 
20 n%(i)=n%(i+1)+e%*d%(i):s%(i)=s%(i+1)+p%(d%(i)):m=(n%(i)-d%(i))/6:
   IF i>0 AND 6*m>i*p%(9) THEN 80                                   REM *** Calcul N S et sixième de la différence
30 IF i=1 THEN BEGIN                                                REM *** Avant-dernier chiffre - solution possible?
40   IF m<0 OR m<>INT(m) THEN 70:ELSE d%(0)=.516685+SQRT(m):BEND    REM *** si oui donner une première estimation
50 IF i>0 THEN e%=e%/10 : i=i-1 : GOTO 20                           REM *** Boucle détermine tous les autres chiffres
60 if m<0 THEN 80 : ELSE IF m=0 THEN PRINT n%(0),                   REM *** Arrêt dernier chiffre ou affichage solution
70 d%(i)=d%(i)+1:IF d%(i)<=9 THEN 20                                REM *** chiffre suivant sans dépasser 9
80 d%(i%)=0:e%=10*e%:i=i+1: if i<4 THEN 70                          REM *** sinon remonter au précèdent
90 PRINT "." : END                                                  REM *** dernière ligne

C'est un bel exemple de BASIC en spaghettis !
Il s'agit de la version recherchant les entier jusqu'à 3000 (exclu)

[dprtl]

Voici ma version pour PB-1000, qui teste tous les nombres de 0 à 1000 en 44 secondes environ :

Code : Tout sélectionner

10 DIMX(10)
20 FOR U=0 TO9:X(U)=U^3:NEXT
30 S=0:FOR C=0 TO9
40 FOR D=0 TO9:T=X(C)+X(D)
50 FOR U=0 TO9:IF T+X(U)=S THENPRINTS
60 S=S+1:NEXT:NEXT:NEXT:BEEP

[zpalm]

Sur HP Prime, moins de 3 dixièmes de seconde pour parcourir les nombres de 0 à 1000:

[dprtl]

Sur HP Prime, moins de 3 dixièmes de seconde pour parcourir les nombres de 0 à 1000

Tellement rapide, que ça ne vaut même plus le coup de chercher à optimiser

[Marge]

J'essaie d'écrire le pgm le plus lent, mais c'est lent.

[Marge]

Ça y est ! ça tourne bien.

Bon, j'ai un peu triché en commençant sous 1000, mais à l'heure où j'écris, ça fait près d'une demi-heure que la 29c mouline - elle a tout de même trouvé 4 solutions. J'ai lancé la 19c environ 10 minutes après... je ferai un comparatif des temps respectifs demain, avec PAUSE sur la 29c, ça peut être intéressant.
Le programme, balourd bien sûr, comme l'algorithme :

Code : Tout sélectionner

9
9
9
STO 0
LBL 0
1
0
/
ENTER
FRAC
1
0
x
ENTER
ENTER
x
x
STO 1
Rd
INT
x=0?
GTO 9
1
0
/
ENTER
FRAC
1
0
x
ENTER
ENTER
x
x
STO+1
Rd
INT
x=0?
GTO 9
ENTER
ENTER
x
x
STO+1
LBL 9
RCL 0
RCL 1
x=y?
R/S (29c) PRx (19c)
DSZ
GTO 0
RTN

53 pas, 2 mémoires, soit 67 octets.
Ne me faites pas rougir en essayant de l'améliorer (mince, raté), c'est du brut.

La 19c semble plus lente... mais ça tient dans les trente-quarante minutes. (!) Ce sont tout de même des machines des années 70 !

[C.Ret]

Sur HP Prime, moins de 3 dixièmes de seconde pour parcourir les nombres de 0 à 1000

Tellement rapide, que ça ne vaut même plus le coup de chercher à optimiser

N'empêche que j'ai aussi rapide qu'une HP Prime sur mon SHARP PC-1211 !
Sauf si j'allume l'imprimante, il me faut alors 3 secondes de plus qu'une HP Prime

[gege]

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.