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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3419
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 »

Ah! Pas mal. J'aime bien l'utilisation de la liste pour "boucler" la somme des 'd derniers termes ou chiffres'.

Ce type de language est quand même bien plus lisible que le RPL qui avec sont utilisation tacite de la pile est trop vite isotérique (même pour l'auteur du code).

Il resemble beaucoup à celui de la HP-39gii avec cependant une économie de syntaxe (par exemple pour les argument de la boucle FOR) qui me font un peu penser à du C (alors que le language de l'HP-39 est plus proche d'un BASIC ou du PASCAL).

En tout cas, on retrouve bien dans la fonction ISKEITH() la structure de nos précèdent code: décomposition de l'entier puis le calcul itératif des sommes de 'd derniers termes' de la suite jusqu'à égaler ou dépasser l'entier.

Et la procédure appelante a l'avantage de bien mettre en évidence le double aspect du problème posé; déterminer si un nombre est un nombre de Keith, puis si ce n'est pas le cas aller chercher (parfois loin) le nombre Keith suivant.


J'attends toujours les versions pour les HP classiques (RPN) et des anciennes TI (AOS).
Je vais essayer de composer une version pour HP-19c et peut-être pour HP-25C.
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 : 5259
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

C.Ret a écrit : Comme d est définie au début du programme, je ne peux pas utiliser une boucle WHILE/REPEAT car sinon il y aurait une erreur si n change de dimension (passe de 2 à trois chiffres par exemple). L'appel récursif me paraissait la meilleure solution come cela d est définit pour chaque n.
merci C.Ret pour cette remarque, je n'avais pas fait attention à cela. Mon programme ne fonctionne donc pas correctement dans tous les cas.

Voici une nouvelle version qui tient compte de cela, et qui optimise également l'utilisation de la dimention du nombre (merci C.Ret).
Cette version donne le bon résultat pour 99.

Par contre ette version est un peu plus lente que la précédente :
15 sec pour 700 et
190 sec pour 7000

Code : Tout sélectionner

<< 0 -> C 
  <<
    WHILE
      DUP DUP LOG IP DUP 'C' STO 1 
      FOR I
        I ALOG MOD LASTARG / IP SWAP
      -1 STEP 
      DO 
        C 1 + DUPN
        1 C START + NEXT
        C 2 + ROLL DROP
      UNTIL
        DUP C 3 + PICK >=
      END
      C 1 + ROLLD
      C DROPN
      OVER <>
    REPEAT
      1 +
    END
  >>
>>
Taille : 190 octets

EDIT : par contre ce programme ne fonctionne pas pour N < 10, il faudrait ajouter un test au début.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 454
Enregistré le : 13 janv. 2013 19:44
Localisation : Marseille-est

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

Message par babaorhum »

Ahhh, je relance le duel ancestral : HP vs TI !!!!

et, c'est nouveau pour moi, j'ai la TI !!

C'est vrai que le code TI-92 est très proche de celui de Tyann sur HP39gii. Par contre au niveau des temps de calcul ... je suis un peu à la rue ...

Quelques chiffres pour les versions TI-92 donnée un peu plus haut :
IsKeith : 268 octets
FindKeith : 223 octets

je lance FindKeith
nn? -> 700
"non ce n'est as un Keith" en 1''30 (approximatif, chronos réalisés avec HP-41 ...)
Keith suivant = 742 en 32''30 (toujours a peu près ...)

nn? -> 7000
"non ce n'est as un Keith" en 1''50
Keith suivant = 7385 en 6'01'' (cohérent avec les temps de Bernouilli92)

par contre pour 70000, à la louche, le TI-92 devrait arriver à 86935 en ... 26 heures et des poussières (estimation basée sur 1 minute de calcul pour analyser les nombres de 70000 à 70050 !!) ...la hp39gii de Tyann est foudroyante !!

????
BaBaoRhum
HP J728,200LX,1000CX,75C,71B,48GX,42s,41CX,32E,32Sii,28S,22s,21,16C,11C
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74,92,95 ; Canon X-07 ; TANDY EC-4026 ; Wp34S
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3637
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat »

babaorhum a écrit :C'est vrai que le code TI-92 est très proche de celui de Tyann sur HP39gii. Par contre au niveau des temps de calcul ... je suis un peu à la rue ...
Sauf erreur, le programme de Tyann est sur nSpire, donc normal que ça ressemble à la TI-92 ! :wink:
Avatar du membre
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 454
Enregistré le : 13 janv. 2013 19:44
Localisation : Marseille-est

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

Message par babaorhum »

Merci Hobiecat !
Hobiecat a écrit :
babaorhum a écrit :C'est vrai que le code TI-92 est très proche de celui de Tyann sur HP39gii. Par contre au niveau des temps de calcul ... je suis un peu à la rue ...
Sauf erreur, le programme de Tyann est sur nSpire, donc normal que ça ressemble à la TI-92 ! :wink:
c'est vrai .... (j'ai lu trop vite ...) ... donc normal que ca ressemble ...

n'empèche que ca va drolement vite la nspire ...
BaBaoRhum
HP J728,200LX,1000CX,75C,71B,48GX,42s,41CX,32E,32Sii,28S,22s,21,16C,11C
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74,92,95 ; Canon X-07 ; TANDY EC-4026 ; Wp34S
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3419
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 »

En attendant qu'il soit l'heure de dévoilé les codes vraiment rapide, voici encore un code 'lent' car explorant systématiquement tous les entiers.

Je n'ai pas eut le temps de mettre au point celui pour HP-19C (désolé Marge) et encore moins celui pour HP-25C, voici en attendant mieux, un code certainement optimisable pour HP-41C.

J'ai cherché à n'utiliser que le nombre minimal de registres. Pour un entier de (d+1) chiffres, les registre R_0 à R_d sont utilisés ainsi que le registre R11 qui me sert d'indice pour les adressages indirects. Pour compter de d à 0, j'utilise ISG, mais peut-être est-ce une erreur un code basé sur DSE serait plus efficace ? :?:

Par contre, la valeur de l'entier n'est pas copiée dans un registre, elle se promène dans la pile tout au long de ce code qui boucle sur lui-même jusqu'à trouver un nombre de Keith.

Aucun test n'est fait pour éviter les résultat aberrant pour n<10 , ni la recherche infinie pour n>9E9 (en fait je ma rend compte que j'aurais pu me limiter à R0: à R9 et R10 pour mémoriser d :x )

Code : Tout sélectionner

               t:  z:  y:       x:       L:       R0:R1:R2:R3:R4:R5:R6:R7:R8:R9:R10:R11:// Commentaires
                                                                                        
001 LBL "NKEITH                 n                                                       
002 LBL 00                      n                                                       
003 0                  n        0                                                       
004 XEQ 11             n        0        d                                         -d   // initialise pointeur des registre (R11)
005 LBL 01             n        sum                                                     
006 RCL Y          n   sum      n                                                       
007 RCL 11     n   sum n        -i                                                      
008 10^X       n   sum n        10^-i    -i                                             
009 x              n   sum      n.10^-i  10^-i                                          
010 INT            n   sum      abcd     n.10^-i                                        
011 10         n   sum [n/10^i] 10                                                      
012 MOD            n   sum      c_i      10                                             
013 ST0 IND 11                                    c  c  c  …  c  c  c                   
014 +                  n        sum'     c_i                                            
015 ISG 11                                                                          1-d 
016 GTO 01     k                                                                        // boucle pour de d à 0 inclus
017 LBL 02             n        t                                                   1   // t est le dernier terme de la suite
018 XEQ 11             n        t        d                                          -d  // initialise pointeur des registres
019 LBL 03             n        t                                                       
020 x=y ?              n        t                                                       
021 RTN                                                                                 // n=t donc n est nombre de Keith; ARRET
022 x>y ?              n        t                                                       
023 GTO 04                                                                              // t>n donc vers n suivant
024 RETURN^        n   t        t                                                       
025 +                  n        2t       t                                              
026 LASTx          n   2t       t                                                       
027 x<> IND 11     n   2t       a                 c  c  c  …  t" t' t                   // mémorise terme à la place chiffre
028 -                  n        2*t-a    a                                              // calcul terme suivant 
029 ISG 11             n        t'                                                      
030 GTO 03                                                                              // boucle R11 pour mémoriser touts les ter
031 GTO 02                                                                              
032 LBL 04             n        t                                                       
033 SIGN               n        1        t                                              
034 +                           n+1                                                     
035 GTO 00                                                                              // recommence avec entier suivant (n+1) 
036 LBL 11         ~~  n        s                                                   ~   // sous-programme initialisation pointeur 
037 RCL Y      ~~  n   s        n                                                       
038 LOG        ~~  n   s        lg n     n                                              
039 INT        ~~  n   s        d        lg n                                           
040 CHS        ~~  n   s        -d       d                                              
041 STO 11     ~~  n   s        -d                                                  -d  // mémorise d dans registre R11
042 RDN        -d  ~~  n        s                                                       
043 RTN            ~~  n        s        d                                          -d  // les registres  Y: et X: sont conservés 

Octets: 84 + 12 * 7 = 168 octets env.

Vitesse :
10 --> 14 ( 0'21" )
28 --> 28 ( 0'03" )
70 --> 75 ( 0'29" )
700 --> 741 ( 4'14" )
7000 --> 7385 ( 50'23" )

On retrouve presque ligne à ligne l'algorithme de mon code pour HP-28S:
LBL 00 - label pour boucle sur lui-même (tester n, puis n+1, n+2, ...) ce n'est pas obligatoire, mais ce doit être plus court que de saisir GTO NKEITH

LBL 01 - boucle qui met les chiffres de l'entier n dans les registres R_d: à R00: avec le premier chiffre en R_d: et le dernier en R00:

Pour cela le registre R11: contient (-d) qui est incrémenté à chaque fois. Le sous-programme LBL 11 permet de remettre R11: à la valeur initiale.

LBL 02 et LBL 03 - boucle de calcul des termes de la suite.
Le terme suivant est calculé à l'aide du dernier terme t par la formule t_(i+1) = 2*t_(i) - t_(i-d) où le premier terme t_(i) est la somme des (1+d) chiffres de l'entier n.
Au fur et à mesure du calcul des termes, ceux-ci sont mémorisés dans le registre R_i: qui servait à mémoriser soit le chiffre de l'entier soit le terme d-précédant t_(i-d)

La boucle passe par LBL 02 chaque fois qu'il faut réinitialiser R11: à la valeur initiale (à l'aide du sous-programme XEQ 11).

LBL 04 - Fin de test, en cas de dépassement, on relance (GTO 00) avec (n+1) notons en passant l'utilisation de SIGN pour MPO'iser le calcul de (n+1).

LBL 11 - Sous-programme de réinitialisation de R11: à (-d) à partir du logarithme de n qui se trouve à chaque appel au niveau y: de la pile.
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
tyann
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 846
Enregistré le : 06 oct. 2012 14:37

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

Message par tyann »

Bonsoir à tous
Oui je confirme mon code est sur nSpire et non sur hp39gii(j'avais laissé celle-ci à notre grand spécialiste Gilles59) :wink:
Et le code de nspire est entiérement compatible avec la Ti92.
C'est vrai qu'elle est rapide la cx , hein Tipoucet :wink:
Si seulement Ti daignais nous pondre un Basic digne de ce nom.
(Ils pourraient pas embaucher Franck Ostrowski) :tongue: :tongue: :tongue:
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
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

tyann a écrit :Bonsoir à tous
Oui je confirme mon code est sur nSpire et non sur hp39gii(j'avais laissé celle-ci à notre grand spécialiste Gilles59) :wink:
C.RET M'A TUER

avec ses temps annoncés pour HP28 8O :D

J'a bien trouvé un genre de trame dans la suite des nombres mais je n'en ai rien sorti. Suis cuirieux de son algo !
Sinon j'ai une version tres courte <100 octets sur 50G mais tres lente et en plus elle utilise une library

L'idée générale c'est DUP ΣLIST + TAIL

et ->STR Chars STR-> (Chars est dans l'excellent librairie GOFER LIST)

1234 donne { 1 2 3 4 }

dommage que TAIL n'existe pas sur 39GII
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 : 3419
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 »

Bo, je crois qu'il est temps de donner un aperçu de mon code explosif :

En fait c'est très simple, et si charo était là il dirait, c'est de la gruge !

Code : Tout sélectionner

«  -> n
  « 
    { 14 19 28 47 61 75 
      197 742 
      1104 1537 2208 2580 3684 4788 7385 7647 7909 
      31331 34285 34348 55604 62662 86935 93993 
      120284 129106 147640 156146 174680 183186 298320 355419 694280 925993 
      1084051 7913837 
      11436171 33445755 44121607 
      129572008 251133297 
      24769286411 96189170155 
      171570159070 202366307758 239143607789 296658839738 }
    1
    DO
       GETI
    UNTIL n >= END
    GET
  »
»
Voilà, le principe est très simple, les Nombres de Keith sont mémorisés et une boucle parcourt cette liste jusqu'à trouver le premier Nombre de Keith supérieur (ou égal) à l'entier demandé.
Notons au passage l'utilisation de GETI qui prend un élément de la liste (comme GET) et qui de plus met à jour l'indice pour préparer le terrain au prochain GETI, ou GET qui lui consomme liste et indice.


En BASIC pour Pocket et 8 bits, cela donnerait quelque chose comme cela :

Code : Tout sélectionner

10 DATA 14,19,28,47,61,75
20 DATA 197,742
30 DATA 1104,1537,2208,2580,3684,4788,7385,7647,7909
40 DATA 31331,34285,34348,55604,62662,86935,93993
50 DATA 120284,129106,147640,156146,174680,183186,298320,355419,694280,925993
60 DATA 1084051,7913837
70 DATA 11436171,33445755,44121607
80 DATA 129572008,251133297

100 DO
110 :INPUT "N=";N
120 :IF N<10 THEN EXIT
130 :RESTORE
140 :DO:READ K:LOOP UNTIL K>=N
150 :PRINT "   ";K
160 :PRINT
170 LOOP
180 END

Pour le SHARP PC-1211, pas de DATA il faut affecter les variables une à une ce qui prend plein d'octets (chaque chiffre fait 1 octet) et ensuite chaque nombre prend les 8 octet du registres. Seule solution viable, utiliser l'interface cassette :

Code : Tout sélectionner

1:INPUT #"KEITHNB";C                 // Charge les Nombre Keith depuis la cassette (ou le fichier wav)
2:"K"INPUT "N=";A:B=2                // Demande saise d'un entier
3:B=B+1:IF A(B)<A GOTO 3             // boucle tant que le nombre de keith est trop petit
4:PRINT A,A(B):B=B+1:A=A(B):GOTO 2   // Affiche l'entier et le nombre de keith immédiatement suivant
                                     // (ou eventuellement deux fois l'entier si c'est un Nombre de Keith)
Octets: 76 programmes + 43 registres (de A=A(1) à A(43)) = 76 + 344 = 420 octets.
Vitesse:les résultats mettent moins de 35 secondes à apparaitre, une fois le fichier de données récupéré depuis l'interface.

Mise en place / Première utilisation:
-----------------------------------------------

Installer le SHARP PC-1211 sur son berceau CE-121 ou CE-122.
Positionner la cassette au début de la bande (ou lancer la lectuere du fichier wav en boucle).
Connecter l'interface à son lecteur de cassette sans oublier de brancher le jack 'remote controle'.
Sur la CE-122 ne pas oublier de positionner le commutateur REMONTE sur la position ON.
Charger le programme : CLOAD "KEITH" depuis la cassette (ou le fichier wav)
Ajuster le niveau sonnore.
A la fin du chargement, la bande s'arrête et on lance l'initialisation :
RUN le SHARP PC-1211 charge les données depuis la cassette (ou le fichier WAV).

Utilisations ultérieure:
----------------------------
Pour déterminer le Nombre de Keith suivant ou vérifier qu'un entier est un nombre de Keith, en mode DEF faire [shift]+[ K ] et saisir l'entier.
Le résultat s'affiche rapidement ou s'imprime. LE SHARP peut être utiliser sans son interface cassette.

Pour lister les Nombres de Keith, entrer un premier entier comme ci-dessus puis appuyer sur [ENTER] pour faire apparitre l'écran de saisie suivant et valider par [ENTER] sans saisir d'entier, les Nombres de Keith seront listés deux par deux à chaque tours de roue.
Si l'on rentre un entier trop grand, le SHARP boucle lontemps, deux minutes environ et s'arrête sur un message d'erreur 4 à la ligne 3.

Génération du fichier et programme:
------------------------------------------------
Le fichier "KEITHNB" contient les 41 premiers nombres de Keith:

La ligne 1 du programme la charge à partir du registre C

Pour générer ce fichier, le programme suivant peut être utilisé :
10:"L" INPUT "ENTER 1,PRESS PLAY";A:IF A INPUT #"KEITHNB";C
20:"=" FOR B=130 TO 173:IF A(B)=0 INPUT "K.N.=";A(B)
30:PRINT A(B):NEXT B
40:"S" INPUT "PRESS REC+PLAY,ENTER 1";A:IF A PRINT #"KEITHNB";A(130)

P.S.:
Je n'ai pas réussit à mettre mon fichier WAV (en fait un WMA) en ligne - je ne suis pas à la maison mais en déplacement - . Il est disponible en pièce jointe par MP si quelqu'un a un site où l'on peut le mettre en libre téléchargement.
Modifié en dernier par C.Ret le 25 févr. 2013 12:30, modifié 2 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 : 5259
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

C.Ret a écrit :Pour le SHARP PC-1211, pas de DATA il faut affecter les variables une à une ce qui prend plein d'octets (chaque chiffre fait 1 octet) et ensuite chaque nombre prend les 8 octet du registres. Seule solution viable, utiliser l'interface cassette :
Il n'y a pas moyen d'utiliser un tableau de nombres et d'affecter chacun des éléments ?
Quelque chose du genre :

Code : Tout sélectionner

10 DIM A(47)
20 A(1)=14:A(2)=19:A(3)=28:A(4)=47:A(5)=61:A(6)=75
30 A(7)=197:A(8)=742
etc..
HP, Casio, Sharp, Psion, quelques TI et divers autres
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 »

C.Ret a écrit :En fait c'est très simple, et si charo était là il dirait, c'est de la gruge !
Je pense que Charo est tombé dans une embuscade de machines Casio et qu'il ne s'en est pas sorti cette fois.

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

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

Message par Gilles59 »

C.Ret a écrit :Bo, je crois qu'il est temps de donner un aperçu de mon code explosif :

En fait c'est très simple, et si charo était là il dirait, c'est de la gruge !
Et il n'aurait peut-être pas tout à fait tord :wink:

Code : Tout sélectionner

    «
    
    { 14 19 28 47 61 75
      197 742
      1104 1537 2208 2580 3684 4788 7385 7647 7909
      31331 34285 34348 55604 62662 86935 93993
      120284 129106 147640 156146 174680 183186 298320 355419 694280 925993
      1084051 7913837
      11436171 33445755 44121607
      129572008 251133297
      24769286411 96189170155
      171570159070 202366307758 239143607789 296658839738 }
      
      SWAP OVER <= SWAP IFT  HEAD
     »
Une version en 431.5 octect (mode Exact) , qui utilise le traitement de listes (49/50 et peut etre 48G ?)
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
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5259
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

Gilles59 a écrit :
C.Ret a écrit :Bo, je crois qu'il est temps de donner un aperçu de mon code explosif :

En fait c'est très simple, et si charo était là il dirait, c'est de la gruge !
Et il n'aurait peut-être pas tout à fait tord :wink:

Code : Tout sélectionner

    «
    
    { 14 19 28 47 61 75
      197 742
      1104 1537 2208 2580 3684 4788 7385 7647 7909
      31331 34285 34348 55604 62662 86935 93993
      120284 129106 147640 156146 174680 183186 298320 355419 694280 925993
      1084051 7913837
      11436171 33445755 44121607
      129572008 251133297
      24769286411 96189170155
      171570159070 202366307758 239143607789 296658839738 }
      
      SWAP OVER <= SWAP IFT  HEAD
     »
Une version en 431.5 octect (mode Exact) , qui utilise le traitement de listes (49/50 et peut etre 48G ?)
Je confirme, cela fonctionne sur 48g.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3419
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 »

bernouilli92 a écrit :
C.Ret a écrit :Pour le SHARP PC-1211, pas de DATA il faut affecter les variables une à une ce qui prend plein d'octets (chaque chiffre fait 1 octet) et ensuite chaque nombre prend les 8 octet du registres. Seule solution viable, utiliser l'interface cassette :
Il n'y a pas moyen d'utiliser un tableau de nombres et d'affecter chacun des éléments ?
Quelque chose du genre :

Code : Tout sélectionner

10 DIM A(47)
20 A(1)=14:A(2)=19:A(3)=28:A(4)=47:A(5)=61:A(6)=75
30 A(7)=197:A(8)=742
etc..
C'est possible, mais il y a 43 valeurs à saisir donc on peut faire le total des octets:
':A(xx)=' fait 7 octets x43 donne 301 octet (en réalité ~292 car il y quelque indice à un seul chiffre et des : inutiles en début de ligne).
Les 43 nombres se répartissent de la façon suivante :
6 nombres à 2 chiffres 12 octets
2 nombres à 3 chiffres 6 octets
9 nombres à 4 chiffres 36 octets
7 nombres à 5 chiffres 35 octets
10 nombres à 6 chiffres 70 octets
2 nombres à 7 chiffres 14 octets
3 nombres à 8 chiffres 24 octets
2 nombres à 9 chiffres 18 octets

Ce qui donne un total de 516 octets de données qu'il faut répartir par ligne de 80 caractères max.

Ce qui fait, au mieux, 7 lignes soit 21 octets de plus (deux pour le n° de ligne et un pour le CRet de fin de ligne)

Le programme pèse donc environ 600 octets programmes (si on se débrouille bien) et utilise donc 44 variables soit en tout 952 octets Donc cela effectivement entre dans le SHARP PC-1211.

C'est vrai que j'ai décidé d'utiliser l'interface cassette en considérant les 71 nombres que j'ai trouvé sur Internet, et qu'alors cela n'entre pas (à cause des nombre à beaucoup de chiffre). En faisant mon estimation, je n'avais pas réalisé qu'il en fallait moins pour un SHARP limité à 10 chiffres ! :evil:


Paul Tergeist a écrit :Je pense que Charo est tombé dans une embuscade de machines Casio et qu'il ne s'en est pas sorti cette fois.
YES : 1664
YES YES YES YES
Espèrons que Charo ne s'est pas fait mal !
Gilles59 a écrit :
C.Ret a écrit :Bo, je crois qu'il est temps de donner un aperçu de mon code explosif :

En fait c'est très simple, et si charo était là il dirait, c'est de la gruge !
Et il n'aurait peut-être pas tout à fait tord :wink:

[.. excellent code ...]

Une version en 431.5 octect (mode Exact) , qui utilise le traitement de listes (49/50 et peut etre 48G ?)
Pour gagner des octets, on peut aussi ne pas saisir le tableau de nombre, mais le compressé.
Une première façon de faire est de faire par différentiel.

On sait que le premier Nombre de Keith est 14, au lieu de mémoriser les nombre (ce qui prend de plus en plus de place avec l'ugmentation progressive du nombre de chiffre) on se limite à donner les écarts entre les nombres succéssifs. Leur nombre de chiffre augmente aussi, mais moins vite.

Dans un second temps, on peut aussi réduire ces valeur diffèrentielle à l'aide d'une fonction de croissance (par exemple valeur moyenne linéaire ou autre). On indique alors pour chaque rang l'écart à cette valeur moyenne. Si la fonction de croissance est bien foutue, et que tout est à peu près juste à +/-99 ou +/-999, alors les écarts ne font que deux ou trois chiffres.

Mais l'extraction des nombre de keith devient alors bien plus compliquée. Tout dépend de la fonction de croissance.
Il faut donc trouver un compromis pour miser petit !!
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
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 454
Enregistré le : 13 janv. 2013 19:44
Localisation : Marseille-est

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

Message par babaorhum »

Quel coquin ce C.ret !!!

... mais le précédent MPO nous avait mis sur la piste de "l'autre façon de voir les choses" !!
On se doutait un peu quand même vu les perfs annoncées sur 28S ...

sinon bien le code HP-41 - pas pris le temps de creuser pour chercher à optimiser - en fait on a fait tous a peu près la même chose dans la version "calcul bourrin".

D'ailleur j'ai fais un petit comparatif avec mes "mamies basic" avec le "calcul bourrin keith" (les benchs sont à la mode sur MySilicium en ce moment ... :wink: ).

Donc sur la rangée de départ :

Sharp PC-1500 // Casio FX-880P // HP-75C

et le programme Keith en basic (bourrin) :

Code : Tout sélectionner

5 REM - CALCUL KEITH - MPO 39 - PC1500
10 DIM N(10):WAIT 0
20 INPUT "NBRE ?",N1
30 GOSUB 300 : GOSUB 200
40 IF R=1 THEN PRINT N1;" est un keith"
50 IF R=0 THEN PRINT N1;" n'est pas un keith"
55 REM - RECHERCHE DU KEITH SUIVANT -
60 N1 = N1+1 : GOSUB 300 : GOSUB 200 : IF R=0 THEN GOTO 60
130 WAIT : PRINT "keith suivant est : " ; N1
140 END
200 REM  - SSP IS KEITH ? -
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 LET R=0 : RETURN
240 IF N(L)=N1 THEN LET R=1 : RETURN
250 GOTO 210
300 REM - SSP DECOMPOSTION
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
adapté lègèrement pour chaque machine (... que INT sur sharp, INT et FRAC sur casio, IP et FP sur HP ... plus qq autres broutilles d'orthographe adaptées à chacune)

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 ...

Et comme j'ai programmé les 3 machines à la suite, je classe aussi le PC-1500 premier en terme de facilité d'emploi !!! (mon ordre est : PC-1500 ; FX-880P et son écran à 2 lignes ; HP-75C et son clavier trop rigide pour taper vite ... et l'écran un peu "jaune" reste assez peu lisible en luminosité moyenne). Mais ceci est subjectif !!!

voilà voilà ...
BaBaoRhum
HP J728,200LX,1000CX,75C,71B,48GX,42s,41CX,32E,32Sii,28S,22s,21,16C,11C
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74,92,95 ; Canon X-07 ; TANDY EC-4026 ; Wp34S
Répondre

Retourner vers « Tous les Pockets »