Misez p'tit, Optimisez - N°39 (Nombres de Keith)

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

Avatar du membre
Paul Tergeist
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2417
Enregistré le : 15 oct. 2007 15:50
Localisation : 3ème planète après le soleil

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Paul Tergeist »

Oui ce n'est pas bête; J'avais bien pensé à codifier toutes les instructions
par exemple 1 pour LBL, 2 pour STO, etc... mais je comptais encore
les mettre dans une liste et j'étais aussi coincé, je n'avais pas pensé à un vecteur...
Et je n'avais surtout pas pensé à leur donner leur codification...
Et encore moins faire de la programmation synthétique...

Je vais attendre car à supposer que HP libère une ROM qui corrige le pb des listes
ou même qu'ils nous donne la possibilité de mouvementer les fichiers
de note par exemple, ce serait Las Vegas et mon système de vecteur deviendrait obsolethe...
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par C.Ret »

Surtout ne fait pas l'erreur de créer ta propre codifition des instruction, utilise celle qui existe déjà, c'est à dire celle utilisée dans les Hp-41, comme cela ton simulateur pourra servir à créer de vrais fichiers *.v41 échangeable avec les autres fans de l'HP-41 et qui donc seront plus facile à transmettre vers une vraie !?!

Image

Bon, d'accord c'est quand même très tordu comme code. Utiliser des listes contenant des chaines de caractères n'est peut-être pas si mal que cela en fait .
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
Paul Tergeist
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2417
Enregistré le : 15 oct. 2007 15:50
Localisation : 3ème planète après le soleil

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Paul Tergeist »

Ca peut être transparent pour l'utilisateur, il n'est pas censé connaître par coeur les codes,
l'interface pourrait juste présenter les mnémoniques.
L'idéal serait que l'on puisse mouvementer par programme un fichier texte (ex hpnotes)
L'utilisateur rentrerait son programme et le simulateur l’évaluerait.

Sinon il y a aussi la possibilité de créer une saisie alpha. Mais une fois que le programme
est saisi, comment le sauver ?

Elle est super intéressante par sa vitesse cette HP-39Gii. On dispose d'un langage
interprété qui donne des performances comparables à du compilé. Du coup,
aucune lourdeur, on modifie le source et hop on l’exécute direct...
C'est super bien joué HP.
Avatar du membre
tyann
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 845
Enregistré le : 06 oct. 2012 14:37

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par tyann »

Bonjour à tous
Je viens de mettre en pratique la méthode de Gilles59. :D

Code : Tout sélectionner

var.monitor("n")
r=0
function sum(l,c)
    local s,d=0,0
    for i,d in ipairs(l) do
        s=s+d
    end
    l[c]=s
end
function keith(n)
 while 1 do
      local s,l,i,li,c
       li={}
       s=tostring(n)
       l=string.len(s)
       for i=1,l do
           li[i]=tonumber(string.sub(s,i,i))
       end
       c=1
       while 1 do
           sum(li,c)
           if li[c]>= n then break end
           c=c+1
           if c>l then c=1 end
       end
       if li[c]==n then
           return n
       else
           n=n+1
       end
   end
end
function on.varChange(n)
 r=keith(var.recall("n"))
 platform.window:invalidate()
end
function on.paint(gc)
    gc:drawString("R="..r,10,20)
end
Nouveau record :70000 en < 26 s.
J'en ai profité pour condenser un peu le code, sur la fonction sum, j'utilise le fait
qu'en Lua les paramètres sont toujours transmis par référence et non par valeur.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Avatar du membre
tyann
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 845
Enregistré le : 06 oct. 2012 14:37

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par tyann »

Ca me fait penser, j'ai toujours regretté que les langages n'offrent pas
une fonction aller appelons la BORNE qui permetterai de définir des valeurs
mini, maxi pour une variable avec une option qui dirait si on bloque la valeur
comme on peut le faire avec MIN ou MAX ou si en cas de dépassement du maxi, on repasse au mini
et inversement du mini au maxi.
Je pense que ça éviterait beaucoup de tests et allégerait pas mal les listing.
C'est peut-être compliqué pour un langage de dévellopement sur Ordi, compilé ou autre,
mais sur nos caltos qui conservent les variables en mémoire et les utilisent en permanence
pour paramétrer leur différents modes de fonctionnement, ça devrait être faisable :?:
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
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°39 (Nombres de Keith)

Message par dprtl »

babaorhum a écrit : D'ailleur j'ai fais un petit comparatif avec mes "mamies basic" avec le "calcul bourrin keith"

[...]

je pars de n=150 en réponse à l'INPUT - et à l'arrivée on a :

Code : Tout sélectionner

                                PC-1500      FX-880P    HP-75C

n'est pas un keith        ~2"50	       ~3"80           ~1"

keith suivant : 197         1'34"           2'25"         24"10   
HP75C largement en tête : 4 fois plus rapide que PC-1500 et 6 fois plus rapide que FX-880P
Donc pas une surprise mais le PC-1500 est nettement plus rapide que le FX-880P pourtant plus jeune de 7 à 10 ans ...
[...]
Pour vérifier ces allégations, j'ai recopié le même programme bourrin en Basic sur FX-850P :

Code : Tout sélectionner

10 DIM N(10)
20 INPUT "N?",N1
30 GOSUB 310:GOSUB 210
40 IF R=1 THEN PRINT N1;"est un Keith"
50 IF R=0 THEN BEEP:PRINT N1;"n'est pas un Keith"
60 N1=N1+1:GOSUB 310:GOSUB 210:IF R=0 THEN GOTO 60
130 BEEP:PRINT "Keith suivant est :";N1
140 END
210 S=0:FOR I = 1 TO L:S=S+N(I):NEXT I
220 FOR I=2 TO L:N(I-1)=N(I):NEXT I:N(L)=S
230 IF N(L)>N1 THEN R=0:RETURN
240 IF N(L)=N1 THEN R=1:RETURN
250 GOTO 210
310 L=INT(LOG(N1))+1:M=N1
320 FOR I=L TO 1 STEP -1
330 N(I)=((M/10)-INT(M/10))*10:M=INT(M/10)
340 NEXT I
350 RETURN
Et là, la FX-850P affiche "n'est pas un keith" en un peu moins de 2", puis 197 en 1'23" environ. On est donc très proche du score de la PC-1500 !

J'imagine que la différence s'explique par un coup classique sur les Casio sans "garbage collector" : Babaorhum aurait-il oublié un "CLEAR" avant de lancer son programme la première fois ?
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°39 (Nombres de Keith)

Message par dprtl »

Voici un code plus compact pour Casio FX-850P ou Z-1, inspiré par les versions précédentes de Babaorhum et C.Ret :

Code : Tout sélectionner

10 DIM N(10)
20 INPUT"N?",N1
30 L=INT(LOG N1)+1:M=N1:S=0
40 FOR I=L TO 1 STEP-1
50 N(I)=M MOD10:S=S+N(I):M=INT(M/10):NEXT
60 I=I+1:IF I>L THEN I=1
70 M=2*S-N(I):N(I)=S:S=M:IF S<N1 THEN60 
80 IF S=N1 THEN BEEP:PRINT S;"est un Keith":END
90 N1=N1+1:GOTO30
Commentaires sur ce programme :
  • L correspond au nombre de chiffres de N1
  • le tableau N() contient les chiffres de N1 au départ (lignes 40 et 50)
  • S contient la somme des chiffres de N1 au départ
  • puis, à partir de la ligne 60, N() contient les termes de la suite de Keith (une sorte de Fibo)
  • ligne 70, pour optimiser le calcul de la "somme" : N(i) = 2*N(i-1) - N(i-L)
Avec 150 en entrée, ce programme n'affiche plus la première étape, facultative, "n'est pas un Keith". Pour calculer directement 197 en 35s environ sur FX-850P, ou 10s sur Casio Z-1.

Avec 7000 en entrée, calcul jusqu'à 7385, en 7min52s environ sur FX-850P, ou 2min12s sur Casio Z-1.
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Ben »

Je déterre ce vieux topic :-)

Etant en congé, j'ai un peu de temps pour jouer avec une HP-39GS. J'apprends à la programmer. J'ai essayé de reproduire le calcul des nombres de Keith.

Je suis un peu déçu des performances, de 7000, elle mets 12 min 5 sec pour arriver à 7385. Pour un processeur ARM à 75 Mhz. Je me demande si le PC-E500 ne ferait pas tout aussi bien.
Evidemment, pas certain que je programme correctement la calculatrice.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2917
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par zpalm »

Ben a écrit :Je déterre ce vieux topic :-)
Je suis un peu déçu des performances, de 7000, elle mets 12 min 5 sec pour arriver à 7385. Pour un processeur ARM à 75 Mhz. Je me demande si le PC-E500 ne ferait pas tout aussi bien.
En fait il y a une couche d'émulation: la 39GS n’exécute pas directement du code ARM mais du code Saturn émulé sur ARM ce qui peut expliquer les performances.

J'en profite pour porter le code de Gilles59 de la 39GII sur la HP Prime
Gilles59 a écrit : Nouvelle version, plus rapide :

Code : Tout sélectionner

EXPORT Keith(n)
BEGIN
 LOCAL s;
 REPEAT
  s:=string(n); N:=SIZE(s); M:=0;
  L1:=MAKELIST(expr(mid(s,I,1)),I,1,N); 
  REPEAT
   T:=ΣLIST(L1);
   M:=M+1; IF M>N THEN M:=1; END;
   L1(M):=T;
   IF T==n THEN BREAK(2); END
  UNTIL T>n END;
  n:=n+1;
 UNTIL 0 END;
T;
END;
Mais çà reste plus lent que LUA, Temps = 175 sec
Le même algo sur LUA (qui évite de 'bidouiller' les listes) devrait améliorer la vitesse.
Voici ce que j'obtient après quelques optimisations, temps: 51 sec pour Keith(70000)

Code : Tout sélectionner

EXPORT Keith(n)
BEGIN
REPEAT
  SIZE(ASC(STRING(n))-48▶L1)▶N;
  REPEAT
   CONCAT(L1({2,N}),ΣLIST(L1)▶T)▶L1;
  UNTIL T>=n;
UNTIL T==(n+1▶n)-1;
T;
END;
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Ben »

zpalm a écrit :En fait il y a une couche d'émulation: la 39GS n’exécute pas directement du code ARM mais du code Saturn émulé sur ARM ce qui peut expliquer les performances.
L'émulation ne vaut que pour l'exécution de programmes?

Voici mon code, soyez indulgent, c'est mon premier programme ;-)

Code : Tout sélectionner

10->A:
DO A+1->A:
0->F:DISP 1;A:
INT(1+LOG(A))->B:
MAKELIST(A,A,1,B,1)->L1:
A*10^-B->D:
FOR C=1 TO B;
D*10->D:
INT(D)->E:
D-E->D:
E->L1(C):
F+E->F:
END:
1->C:
WHILE F<A
REPEAT
IF C>B THEN 1->C:END:
€LIST (L1)->F:
F->L1(C):
END:
IF F==A THEN DISP 3;A:
END:
UNTIL A<A
END:
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°39 (Nombres de Keith)

Message par dprtl »

On parlait du GFA Basic dans un autre fil de discussion sur Silicium, alors je ne résiste pas à l'envie de porter mon programme précédent pour Casio FX-850P. Malheureusement, ce n'est pas un GFA Punch (8 lignes de trop !), mais la lisibilité reste correcte, malgré les variables de type entier, suffixées avec le symbole '%' :

Code : Tout sélectionner

DIM n%(10)
DO
  INPUT "N?",n1%
  PRINT TIME$;"  ";
  DO
    l%=INT(LOG10(n1%))+1
    m%=n1%
    s%=0
    FOR i%=l% TO 1 STEP -1
      n%(i%)=m% MOD 10
      ADD s%,n%(i%)
      DIV m%,10
    NEXT i%
    REPEAT
      INC i%
      IF i%>l%
        i%=1
      ENDIF
      m%=SHL(s%,1)
      SUB m%,n%(i%)
      n%(i%)=s%
      s%=m%
    UNTIL s%>=n1%
    EXIT IF s%=n1%
    INC n1%
  LOOP
  PRINT s%;" est un Keith.  ";TIME$
LOOP
Les temps de calcul sont honorables pour un Basic interprété, sur un 68000 à 8 Mhz des années 80. On est entre 4 et 5 fois plus lent que le Basic de la HP Prime... pourtant beaucoup plus puissante, en théorie :

Image

Comme ce programme est une boucle infinie, on devra l'interrompre par [control] [shift][alt].
Modifié en dernier par dprtl le 02 sept. 2018 14:08, modifié 1 fois.
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Ben »

Je reviens sur les nombres de Keith.

Depuis l’acquisition de la 602P, elle ne me quitte pas. Dans un souci pédagogique, je me suis lancé dans la recherche de ces nombres, histoire de voir comment fonctionnait exactement les mémoires indexées. On encode le nombre et on appuie sur P0 (si le pgm est en P0 ;-)). Evidemment, toutes critiques constructives sont les bienvenues.

Voici mon code, il fait 70 pas

Code : Tout sélectionner

Min19
0 Min17
MR19
log + 1 = INT MIN18 + 1 = MinF

MR19 LBL0 / 10 = Min16 FRAC * 10 = M+17 IND Min18 1 M-18
MR16 INT x=0 GOTO1 GOTO0

LBL1 1 Min18 LBL2 MR17 Min16 - IND MR18 + MR16 IND Min18 =
Min17 - MR19 = x=0 GOTO3 x>=0 GOTO4 1 M+18 MR18 x=F GOTO1 GOTO2
LBL3 "KEITH" HLT LBL4 "PAS KEITH"
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5622
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par ledudu »

Merci pour cette version que j’essaierai en rentrant.
J’aime l’idée que les réponses aux mpo s’étoffent au fil des ans.
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Misez p'tit, Optimisez - N°39 (Nombres de Keith)

Message par Ben »

Une petite variante du programme qui fait chauffer la bête! :-) Il essaie tous les nombres à partir de 11. Je me suis arrêté à 197 ;-)

Code : Tout sélectionner

11 Min19
LBL5
0 Min17
MR19
log + 1 = INT Min18 + 1 = MinF

MR19 LBL0 / 10 = Min16 FRAC * 10 = M+17 IND Min18 1 M-18
MR16 INT x=0 GOTO1 GOTO0

LBL1 1 Min18 LBL2 MR17 Min16 - IND MR18 + MR16 IND Min18 =
Min17 - MR19 = x=0 GOTO3 x>=0 GOTO4 1 M+18 MR18 x=F GOTO1 GOTO2
LBL3 MR19 PAUSE LBL4 1 M+19 GOTO5
Répondre

Retourner vers « Tous les Pockets »