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

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

bernouilli92 a écrit : 31 août 2014 18:09
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.
Cette version tourne en 0,52" en NewRPL (dont 0.5" à 6MHz).Il faut cependant remplacer la ligne
IF OVER == THEN + ELSE DROP END
par
IF OVER == THEN ADD ELSE DROP END

Le NewRPL corrige ici une incohérence du UserRPL au détriment de la compatibité ascendante
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
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 chiffres

Message par C.Ret »

Ca c'est bien que l'opérateur d'addition '+' ne fasse plus exception !

Bon, tout cela m'a fait parcourir tout cet excellent MPO et je trouve qu'il n'y a pas assez de codes en RPN.

J'ai donc sorti mon HP-15C et avec bien du mal, voici un petit bout de code qui trouve les solutions en quelques minutes :

Code : Tout sélectionner

         ┌──────────┐      ┌──────────┐       ┌──────────┐       ┌──────────┐      ┌──────────┐      ┌──────────┐
f A 21.4s│0.        │ 1.8s │1.        │ 13.4s │153.      │ 38.2s │370.      │ 1.8s │371.      │ 6.3s │407.      │1'35.5s
         └──────────┘      └──────────┘       └──────────┘       └──────────┘      └──────────┘      └──────────┘
L'algorithme est celui que j'ai posté plus haut pour SHARP PC-1211 qui précalcule les sixièmes (10.d-d^3)/6
Les LBL correspondent d'ailleurs dans leur fonctionnement aux lignes du code BASIC. Sauf GSB 9 qui est en fait un sous-programme pour l'affichage des solutions.

Code : Tout sélectionner

000-                   020-       0   0      ┙041-   43 20 g x=0?   │061-       8   8      │081-45,40,24   RCL+(i) │
001-42,21,11 f LBL A  ┑021-42,21, 2 f LBL 2  ╕042-43, 5, 0 g CF 0   │062-45,40,.5   RCL+.5 │082-   44 .4   STO .4  │
002-   42 34 f CLR REG│022-   44 .2   STO .2 │043-       1   1      │063-   45 .2   RCL .2 │083-       1   1       │
003-       1   1      │023-   44 25   STO I  │044-      48   .      │064-43,30, 9 g x≥y?   │084-45,30,.5   RCL-.5  │
004-       0   0      │024-   45 .4   RCl .4 │045-       5   5      │065-   22  4   GTO 4  ┿085-   44 .5   STO .5  │
005-   44 .0   STO .0 │025-45,40,24   RCL+(i)│046-      20   x      │066-       2   2      │086-   22  2   GTO 2   ╛
006-       9   9      │026-   43 44 g INT    │047-45,30,24   RCL-(i)│067       40   +      │
007-   44 25   STO I  │027-   43 36 g lastx  │048-43,30, 6 g x≠y?   │068-   22  2   GTO 2  ╛087-42,21, 9 f LBL 9   ╗
                      │028-   44 16 g ABS    │049-   22  3   GTO 3  ┿                       088-   45 .1   RCL .1  ║
008-42,21, 1 f LBL 1  ┑029-43,30, 6   x≠y?   │050-   45 .3   RCL .3 │069-42,21, 4 f LBL 4  ┑089-45,20,.0   RCL×.0  ║
009-   45 .0   RCL .0 │030-   22  3   GTO 3  ┿051-   32  9   GSB 9  ║070-       9   9      │090-45,40,.2   RCL+.2  ║
010-45,20,25   RCL×I  │031-      48   .      │052-43, 6, 0 g F? 0   │071-   45 .1   RCL .1 │091-45,20,.0   RCL×.0  ║
011-   45 25   RCL I  │032-       3   3      │053-   22  3   GTO 3  ┿072-43,30, 9 g x≥y?   │092-      40   +       ║
012-       3   3      │033-       2   2      │054-      34   x<>y   │073-   43 32 g RTN    ╳093-      31   R/S     ║
013-      14   y^x    │034-      14   y^x    │055-       1   1      │074-       1   1      │094-   43 32 g RTN     ╝
014-      30   -      │035-       2   2      │056-   32  9   GSB 9  ║075-      40   +      │
015-       6   6      │036-      20   ×      │                      │076-   44 .1   STO .1 │
016-      10   ÷      │037-   43 44 g INT    │057-42,21, 3 f LBL 3  ┑077-   44 25   STO I  │
017-   44 24   STO (i)│038-43, 4, 0 g SF 0   │058-      33   RDN    │078-       1   1      │
018-42, 5,25 f DSE I  │039-   44 .3   STO .3 │059-43,30, 4 g x≤0?   │079-       5   5      │
019-   22  1   GTO 1  │040-   44 25   STO I  │060-   22  4   GTO 4  ┿080-      20   ×      │
Registres:
R0 à R9 : valeurs des sixièmes B(d) calculées en début de programme pour chaque chiffre d.
R.0 : constante 10
R.1 : a = chiffre des centaines
R.2 : b = chiffre des dizaines
R.3 : c = chiffre des unités
R.4 : z = sixième pour les centaine A(a) = 15a+B(a)
R.5 : y = parité de a et b 0/1 : pair/impair
Le registre d'indirection I est largement utilisé.

Code : Tout sélectionner

000-
001- LBL A
002-   CLR REG  10  STO .0  9  STO I
008- LBL 1  
009-   RCL .0  RCL×I  RCL I  3  y^x  -  6  ÷  STO (i)  DSE I  GTO 1  0
021- LBL 2
022-   STO .2  STO I  RCl .4  RCL+(i)  INT  lastx  ABS  x≠y?  GTO 3
031-   .32  y^x  2  ×  INT  SF 0  STO .3  STO I  x=0?  CF 0
043-   1.5  ×  RCL-(i)  x≠y?  GTO 3
050-   RCL .3  GSB 9  F? 0  GTO 3
054-   x<>y  1  GSB 9
057- LBL 3
058-   RDN  x≤0?  GTO 4
061-   8  RCL+.5  RCL .2  x≥y?  GTO 4
066-   2  +  GTO 2
069- LBL 4
070-   9  RCL .1  x≥y?  RTN 
074-   1  +  STO .1  STO I  15  ×  RCL+(i)  STO .4  1  RCL-.5  STO .5  GTO 2
087- LBL 9
088-   RCL .1  RCL×.0  RCL+.2  RCL×.0  +  R/S  RTN
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.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

Ce sujet m'est revenu en tête pour mon article dans la Gazette sur les bibliothèques "ListExt" et "GoferList" pour HP50g. Difficile de faire plus court :

Code : Tout sélectionner

« 999 LSEQ « DUP I->NL 3 ^ LSUM == » Filter »
Seulement 65 octets mais 95 sec sur la calc.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
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 chiffres

Message par gege »

Bonjour,
On attend avec impatience l'article !
Et les puissances 4, 5 ... ???
A+
G.E.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

gege a écrit : 12 mai 2019 13:52 Bonjour,
On attend avec impatience l'article !
Et les puissances 4, 5 ... ???
A+
G.E.
Puissance 4ieme : 4 solutions < 10000
Puissance 5ieme : 3 solutions < 10000 avec un duo ;D
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

Gilles59 a écrit : 12 mai 2019 23:59
gege a écrit : 12 mai 2019 13:52 Bonjour,
On attend avec impatience l'article !
Et les puissances 4, 5 ... ???
A+
G.E.
Puissance 4ieme : 4 solutions < 10000
Puissance 5ieme : 3 solutions < 10000 avec un duo ;D
A noter que le même programme tourne en 1,37 sec en NewRPL contre plus de 90s en RPL sur la calculatrice alors même qu'il faut écrire I->NL, LSEQ et Filter en RPL (Sur le simulateur PC ca tourne en... 0,007 s). Comme le Newrpl corrige le bug de ΣLIST, LSUM ne sert plus à rien :

Code : Tout sélectionner

LSEQ : «  ➔ a  « 1 a FOR 'a' a NEXT a ➔LIST » »

Filter :  « ➔ liste filtre « liste 1  « IF DUP filtre NOT THEN DROP END » DOSUBS » »

I➔NL : « DUP SIZE ➔ n s 
             «
                IF s 1 == THEN n 
                ELSE 
                  s 1 - 0 FOR 'a' n a a DIGITS -1 STEP 
               END 
               s ➔LIST 
           »
         »
         
Sili :  « 999 LSEQ « DUP I➔NL 3 ^ ΣLIST == » Filter »

retourne {1 153 370 371 407 } en 1,37 sec sur la calc.
 
Le test s ==1 est normalement inutile pour I->NL mais il y a un bug sur les boucles genre FOR a=1 to 1 STEP -1. J'ai signalé ce bug vicieux pour correction.

A noter que La saisie des programmes en NewRPL sur la calculatrice est bien plus pratique avec le système d'autocomplétion.
Modifié en dernier par Gilles59 le 13 mai 2019 19:37, modifié 2 fois.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
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 chiffres

Message par gege »

Bonjour,
En fait il n'y a pas besoin de chercher indéfiniment, il existe une borne supérieure au-delà de laquelle il ne peut y avoir de solutions.
On a donc d'ailleurs toujours un nombre fini de solutions.

Raisonnement (puisqu'on est dans le délire mathématique en ce moment) :
Si le nombre N contient n chiffres et qu'on fait la somme des chiffres à la puissance p,
Alors 10^(n-1) <= N car N a n chiffres,
et N <= n.9^p car les n chiffres de N sont inférieurs ou égaux à 9.
Donc : 10^(n-1) /n <= 9^p
Quand on fait varier n, on trouve pour p (nombre entier) :

n p
3 2
4 3
5 4
6 5
7 6
...

Ce qui se lit par exemple la 3ème ligne : si une solution a 5 chiffres, alors c'est sur un problème de puissance 4 au moins.
Réciproquement, pour une somme des chiffres puissance 3, on a au plus 4 chiffres dans les solutions : N < 1000
Voilà, sauf erreur.
G.E.
Répondre

Retourner vers « Tous les Pockets »