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

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

cgh
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2142
Enregistré le : 30 août 2011 12:23
Localisation : Vous êtes ici -> .

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

Message par cgh »

babaorhum a écrit :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,...
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde
Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par 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^3N 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
Modifié en dernier par C.Ret le 02 déc. 2015 18:13, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par 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
>>
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

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

Message par gege »

Keeper a écrit :Hello :D
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... :cry:

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

G.E.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

gege a écrit : 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.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Keeper
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 237
Enregistré le : 20 juil. 2014 20:01
Localisation : 71

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

Message par Keeper »

gege a écrit :
Keeper a écrit :Hello :D
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... :cry:
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 :wink:
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

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

Message par 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.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par 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)
Modifié en dernier par C.Ret le 31 oct. 2017 09:13, modifié 3 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

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

Message par 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
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm »

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

Image Image
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

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

Message par dprtl »

zpalm a écrit :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 :)
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

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

Message par Marge »

J'essaie d'écrire le pgm le plus lent, mais c'est lent.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

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

Message par 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 :oops: (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 !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

dprtl a écrit :
zpalm a écrit :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 :D
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

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

Message par 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.
Répondre

Retourner vers « Tous les Pockets »