MPO n°66 - Convertisseur en chiffres romains

[cgh]

@cgh, tu peux nous guider un peu sur le fonctionnement de ton pgm stp ? je nage !

Bon en fait j'ai vu qu'il y a deja un programme existant dans la Librairie HP-41C sur HPmuseum. J'ai donc essaye d'utiliser une autre methode. Ceci dit le programme sur HPmuseum fonctionne de la meme facon que les programmes C ou BASIC presentes dans ce fil...

J'utilise les 4 drapeaux 3 a 0, avec 3 pour les milliers, 2 pour les centaines, 1 pour les dizaines et 0 pour les unites. Comme seul un drapeau peut etre leve (SF et FS?), cela me permet de faire un code generique, le choix des diviseurs (1000, 100, 10 ou 1) et des chiffres romains (I, V, X, L, C, D, M) etant choisi en fonction du drapeau qui est leve. Ce qui fait qu'il n'y a qu'une boucle principale (LBL 14) et une sortie "anticipee" (LBL 00 -> Le 0 n'existe pas en chiffres romains). Il y a 3 sous programmes pour chaque type des chiffres : I, X, C, M (LBL 11) et V, L, D (LBL 12); le cas du 9 etant gere d'un maniere particuliere : IX, XC, CM (LBL 09). Apres les autres chiffres, c'est de l'empilement d'appel a 11 et 12. Le programme n'est pas "completement optimise". Je pense que l'on pouvoir faire mieux. Il est plus long que celui de HPmuseum: 154 octets contre 167, mai le E3 de la ligne 4 de HPmuseum necessite le BYTE GRABBER pour etre programme; de meme, le label "A-R" pese III octets contre VI pour "ROMAIN"...

[cgh]

Une version optimisee du programme

Code : Tout sélectionner

 01*LBL "ROMAIN"
 02 CF 00
 03 CF 01
 04 CF 02
 05 SF 03
 06 CLA
 07*LBL 14
 08 ENTER^
 09 FS? 03
 10 1 E3
 11 FS? 02
 12 100
 13 FS? 01
 14 10
 15 FS? 00
 16 1
 17 X>Y?
 18 GTO 13
 19 MOD
 20 X<>Y
 21 LASTX
 22 /
 23 XEQ IND X
 24*LBL 13
 25 RDN
 26 FS?C 01
 27 SF 00
 28 FS?C 02
 29 SF 01
 30 FS?C 03
 31 SF 02
 32 FS? 00
 33 XEQ IND X
 34 FC?C 00
 35 GTO 14
 36*LBL 00
 37 AVIEW
 38 RTN
 39*LBL 03
 40 XEQ 01
 41*LBL 02
 42 XEQ 01
 43*LBL 01
 44 FS? 00
 45 "`I"
 46 FS? 01
 47 "`X"
 48 FS? 02
 49 "`C"
 50 FS? 03
 51 "`M"
 52 RTN
 53*LBL 04
 54 XEQ 01
 55 FS? 03
 56 GTO 03
 57*LBL 05
 58 FS? 00
 59 "`V"
 60 FS? 01
 61 "`L"
 62 FS? 02
 63 "`D"
 64 RTN
 65*LBL 08
 66*LBL 07
 67*LBL 06
 68 XEQ 05
 69 5
 70 -
 71 GTO IND X
 72*LBL 09
 73 FS? 00
 74 "`IX"
 75 FS? 01
 76 "`XC"
 77 FS? 02
 78 "`CM"
 79 END

Le programme affiche maintenant 159 octets au compteur. Si on utilise le meme artifice que sur HPmuseum, c'est a dire remplacer 1 E3 par E3 et 100 par E2 (avec le BYTE GRABBER) et avec un label de 3 lettres (A-R), on arrive a 154 octets
Par contre, le programme est un peu plus lent ...

[cgh]

Bon, une derniere optimisation en CXLI ... pardon 141 octets. En l'etat du bonhomme, je n'arrive pas a faire mieux

Code : Tout sélectionner

 01*LBL "ROMAIN"
 02 CF 00
 03 CF 01
 04 CF 02
 05 SF 03
 06 CLA
 07 1 E4
 08 /
 09*LBL 14
 10 10
 11 *
 12 FRC
 13 LASTX
 14 INT
 15 X#0?
 16 XEQ IND X
 17 RDN
 18 FS? 00
 19 AVIEW
 20 FS?C 00
 21 RTN
 22 FS?C 01
 23 SF 00
 24 FS?C 02
 25 SF 01
 26 FS?C 03
 27 SF 02
 28 GTO 14
 29*LBL 03
 30 XEQ 01
 31*LBL 02
 32 XEQ 01
 33*LBL 01
 34 FS? 00
 35 "`I"
 36 FS? 01
 37 "`X"
 38 FS? 02
 39 "`C"
 40 FS? 03
 41 "`M"
 42 RTN
 43*LBL 04
 44 XEQ 01
 45 FS? 03
 46 GTO 03
 47*LBL 05
 48 FS? 00
 49 "`V"
 50 FS? 01
 51 "`L"
 52 FS? 02
 53 "`D"
 54 RTN
 55*LBL 08
 56*LBL 07
 57*LBL 06
 58 XEQ 05
 59 5
 60 -
 61 GTO IND X
 62*LBL 09
 63 FS? 00
 64 "`IX"
 65 FS? 01
 66 "`XC"
 67 FS? 02
 68 "`CM"
 69 END

[bernouilli92]

Ah si tu pouvais encore optimiser un peu et faire tenir cela en CX octets. Ce serait le top.

[cgh]

Ah si tu pouvais encore optimiser un peu et faire tenir cela en CX octets. Ce serait le top.

Messieurs a vos claviers pour optimiser en CX octets !

[C.Ret]

En attendant de trouver en 110 octets pounr une Hewlett Packard HP-XLI

J'ai en environ CLXXI octets pour SHARP PC-MCCCLX, en utilisant en fait l'algorithme de baborhum, mais un peu "compressé", c'est à dire n'utilisant que les VII symboles de base à savoir M,D,C,L,X,V et I

Code : Tout sélectionner

1:" " AREAD N: RESTORE 5 : READ A,B$ : WAIT 0
2:READ E,F$ : GOSUB 7 : READ A,B$ : GOSUB 7 : A=E : B$=F$: IF A>1 GOTO 2
3:E=0 : GOSUB 7 : PRINT : END 

5:DATA 1000,"M",100,"C",500,"D",10,"X",50,"L",1,"I",5,"V"

7:IF N>=A LET N=N-A : PRINT B$; : GOTO 7
8:IF N>=A-E LET N=N-A+E : PRINT F$;B$;
9:RETURN

[caloubugs]

Joli !

Y a plus qu'à se servir une MDCLXIV après une telle optimisation

[charognard]

Aucun mérite, je sais
Le RESTORE sans paramètre et 1000 > 1E3

Code : Tout sélectionner

1:" " AREAD N: RESTORE : READ A,B$ : WAIT 0
2:READ E,F$ : GOSUB 7 : READ A,B$ : GOSUB 7 : A=E : B$=F$: IF A>1 GOTO 2
3:E=0 : GOSUB 7 : PRINT : END 

5:DATA 1E3,"M",100,"C",500,"D",10,"X",50,"L",1,"I",5,"V"

7:IF N>=A LET N=N-A : PRINT B$; : GOTO 7
8:IF N>=A-E LET N=N-A+E : PRINT F$;B$;
9:RETURN

[bernouilli92]

Comme il n'y a toujours pas de version en RPL, je m'y colle :

Code : Tout sélectionner

<<
  {10 9 5 4} DUP 100 * OVER 10 * + SWAP + 1 +
  {"M" "CM" "D" "CD" "C" "XC" "L" "XL" "X" "IX" "V" "IV" "I"}
  ROT "" 1 13
  FOR I
    4 PICK I GET
    4 PICK I GET
    WHILE
      OVER 5 PICK <=
    REPEAT
      ROT OVER + ROT ROT
      4 ROLL 3 PICK - 4 ROLLD
    END
    DROP2
  NEXT
  4 ROLLD 3 DROPN
>>

Taille : 284,5 octets

Testé sur hp48g(x) mais devrait aussi tourner sur 48s(x) et peut-être sur hp28s (pas sûr)

[C.Ret]

A priori ce dernier code ne fonctionne pas sur HP-28S car il n'est pas possible de faire des calculs sur les listes.

Il faut donc le modifier légèrement en remplacant le calcul sur la chaine par la liste résultat { 1000 900 500 400 100 90 50 40 10 9 5 4 1 } .

Comme charo, j'en profite pour MPOiser un peu (aucun mérite là aussi sauf celui de respecter l'esprit du jeu):

Code : Tout sélectionner

« { 1000 900 500  400 100   90  50   40  10    9   5    4   1  } 
  {   "M""CM" "D" "CD" "C" "XC" "L" "XL" "X" "IX" "V" "IV" "I" } → Val Sym
  « "" SWAP 
    1 13 FOR i
            Val i GET → v
            « WHILE
                 DUP v ≥
              REPEAT
                 v - 
                 SWAP Sym i GET + SWAP
              END »
         NEXT
    DROP » »

En voici un autre, qui utilise l'algorithme "compliqué":

Code : Tout sélectionner

1:                                 28           @ argument N en haut de la pile
« 
  { 1000 500 100  50  10   5   1  }             @ Liste des valeurs
  {   "M" "D" "C" "L" "X" "V" "I" } → Val Sym   @ Liste des symboles

  « "" SWAP                                     @  Initialise chaine romaine
    3 7 FOR i                                   @  Boucle sur les retenues C X et I                                 
       2 1 FOR j                                @    Pour chaque retenue teste les deux valeurs
          0 1 FOR k                             @      Boucle sans ou avec retenue
             Val i j - GET                      
             Val   i   GET k * -   → v          @ Calcule la valeur du symbole 
             « WHILE
                  DUP v ≥                        @ Tant que N >= val alors affiche le symbole correspondant
               REPEAT
                  v - SWAP                       @ Soustrait la valeur à n est traite la chaine romaine
                  IF k THEN Sym i GET + END      @ Cas des symbole composée à l'aide d'une retenue
                  Sym i j - GET + SWAP           @ Ajoute à la chaine romaine le symbole en cours
               END »
          NEXT
       -1 STEP
     2 STEP DROP » »
1:                             "XXVIII"          @ Retourne la chaine romaine correspondant à n

Bon évidemment, cela n'économise pas les octets.

Mais a l'avantage de préenter l'adaptation pour SHARP PC-1211 :

Code : Tout sélectionner

1  " " CLEAR :INPUT Z:U=0,V=€3,W$="M",X=€2,Y$="C":GOSUB 5:V=5X,W$="D":GOSUB 5:X=10,Y$="X":GOSUB 5:V=50
2  W$="L":GOSUB 5:X=1,Y$="I":GOSUB 5:V=5,W$="V":GOSUB 5:X=0:GOTO 5

3 U=U+1,A$(U)=Y$,Z=Z+X
4 U=U+1,A$(U)=W$,Z=Z-V
5 IF Z>=V GOTO 4
6 IF Z>=V-X GOTO 3
7 V=X,W$=Y$:IF Z RETURN

8 PRINT A$;B$;C$;D$;E$;F$;G$;H$;I$;J$;K$;L$;M$;N$;O$;P$;Q$;R$;S$;T$:END


où € correspond à la touche d'exponation décimale [Exp] du clavier numérique.

[zpalm]

Voici deux programmes pour HP Prime, rien de révolutionnaire après tout ce qui a déjà été fait.

Le premier avec des grandes listes:

Code : Tout sélectionner

EXPORT n,s;
EXPORT ROMAIN(N)
BEGIN
  LOCAL r:={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
  LOCAL d:={1000,900,500,400,100,90,50,40,10,9,5,4,1};
  n:=N;s:="";
  EXECON("WHILE n≥&2 DO s:=s+&1;n:=n-&2;END",r,d);
  RETURN s;
END;

Le deuxième avec des petites listes (juste les 7 lettres romaines) et la gestion des retenues C, X et I:

Code : Tout sélectionner

EXPORT ROM(N)
BEGIN
  LOCAL r:={"M","D","C","L","X","V","I"};
  LOCAL d:={1000,500,100,50,10,5,1,0,0};
  LOCAL j,k,s:="";
  FOR j FROM 1 TO 7 DO
    WHILE N≥d(j) DO s:=s+r(j);N:=N-d(j);END;
    k:=j+j MOD 2+1;
    IF N≥d(j)-d(k) THEN s:=s+r(k)+r(j);N:=N-d(j)+d(k);END;
  END;
  RETURN s;
END;

[Marge]

Voici deux programmes pour HP Prime, rien de révolutionnaire après tout ce qui a déjà été fait.

Le premier avec des grandes listes:

Code : Tout sélectionner

EXPORT n,s;
EXPORT ROMAIN(N)
BEGIN
  LOCAL r:={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
  LOCAL d:={1000,900,500,400,100,90,50,40,10,9,5,4,1};
  n:=N;s:="";
  EXECON("WHILE n≥&2 DO s:=s+&1;n:=n-&2;END",r,d);
  RETURN s;
END;

Le deuxième avec des petites listes (juste les 7 lettres romaines) et la gestion des retenues C, X et I:

Code : Tout sélectionner

EXPORT ROM(N)
BEGIN
  LOCAL r:={"M","D","C","L","X","V","I"};
  LOCAL d:={1000,500,100,50,10,5,1,0,0};
  LOCAL j,k,s:="";
  FOR j FROM 1 TO 7 DO
    WHILE N≥d(j) DO s:=s+r(j);N:=N-d(j);END;
    k:=j+j MOD 2+1;
    IF N≥d(j)-d(k) THEN s:=s+r(k)+r(j);N:=N-d(j)+d(k);END;
  END;
  RETURN s;
END;

C'est intéressant : lequel est le plus lourd, au total ? je suppose que c'est le premier, selon la règle : plus de calcul = plus de temps = moins de mémoire...

[zpalm]

C'est intéressant : lequel est le plus lourd, au total ? je suppose que c'est le premier, selon la règle : plus de calcul = plus de temps = moins de mémoire...

Le plus lourd est le second: 0,60KB contre 0,56KB pour le premier. Sur la HP Prime le source est stocké en plus du programme compilé et d'un header comprenant les variables exportées. La taille est donc directement reliée au nombre de caractères du programme source: 251 caractères pour le premier programme et 303 pour le second. Le premier programme a deux variables exportées alors que le second n'en a aucune, la différence au final est faible.

[zpalm]

Si en taille les deux programmes se valent, en temps d'exécution c'est très différent, le deuxième est 13 fois plus rapide: 3 millisecondes contre 40 millisecondes pour la conversion de 1999 par exemple.

Pour mesurer le temps d'exécution en secondes faire par exemple: time(ROMAIN(1999))
puis appuyer 10 fois sur Enter pour exécuter cette commande 10 fois.
ensuite combiner les résultats en une liste avec : MAKELIST(Ans(I),I,1,10) [Sto] L1
et calculer la moyenne avec mean(L1)

[C.Ret]

Surprenant cette diffèrence de vitesse :

Ce qui est sur c'est qu'avec mes macines, pas besoin de répéter les exécutions pour en déduire le temps; tout va suffisament vite pour que je puisse voir défiler les secondes sur ma montre.

J'en profite pour poster trois bricoles :

Une version pour SHARP PC-1211 plus courte (mais tout aussi lente):

Code : Tout sélectionner

1  " " CLEAR :U=0,V=€3,W$="M",Y$="C":INPUT Z
2  GOSUB 4:V=5X,W$="D":GOSUB 5:Y$="X":GOSUB 4:V=50,W$="L":GOSUB 5:Y$="I":GOSUB 4:V=5,W$="V":GOSUB 5

4 X=.1V
5 IF Z>=V   LET U=U+1,A$(U)=W$,Z=Z-V:GOTO 5
6 IF Z>=V-X LET U=U+1,A$(U)=Y$,Z=Z+X:GOTO 5
7 V=X,W$=Y$:IF Z RETURN

9 PRINT A$;B$;C$;D$;E$;F$;G$;H$;I$;J$;K$;L$;M$;N$;O$;P$;Q$;R$;S$;T$:END

où € correspond à la touche d'exponation décimale [Exp] du clavier numérique.

Son équivalent sur SHARP-PC1360 dont la gestion de l'affichage est plus simple:

Code : Tout sélectionner

1 " " AREAD N: RESTORE : WAIT 0: READ V,S$
2 READ P$: GOSUB 4: READ V,S$: GOSUB 5: IF V>1 GOTO 2

3 DATA 1E3,"M","C",500,"D","X",50,"L","I",5,"V"

4 R=V/10
5 IF N>=V   LET N=N-V: PRINT S$;: GOTO 5
6 IF N>=V-R LET N=N+R: PRINT P$;: GOTO 5
7 V=R,S$=P$:IF N RETURN

9 PRINT : END

(La dernière ligne est facultative).

Et une version pour HP-41C

Code : Tout sélectionner

001 LBL "ROMA
      CLA  7  STO 00  CF 00                             037 LBL 01  "~I"  RTN
006   LBL 11
        2  FS?C 00 Clx  X>0? SF 00  ST- 00  X<> Z       040 LBL 02  "~V"  RTN
015   LBL 12
        RCL IND Y  X>Y?  GTO 13                         043 LBL 03  "~X"  RTN
        -  XEQ IND Y 
      GTO 12                                            046 LBL 04  "~L"  RTN

021   LBL 13                                            049 LBL 05  "~C"  RTN
        RCL IND 00  -  X>0? X>Y? GTO 14
        - XEQ IND 00                                    052 LBL 06  "~D"  RTN
        XEQ IND Y  LASTx
031   LBL 14                                            055 LBL 07  "~M"  RTN
        X<> Z  DSE X  GTO 11
        AVIEW                                       .END.
036 STOP

Ce dernier programme ne fonctionne que si l'on a stocké les valeurs 1, 5, 10, 50, 100, 500 et 1000 respectivement dans les registres R01 à R07. Le registre R00 servant d'indice pour les retenues (l'indice des valeurs principales étant dans la pile - souvent au niveau de Y ).

Les valeurs des registres R01 à R07 peuvent ête initialisées à l'aide du programme suivant :

Code : Tout sélectionner

001 LBL "INIRO
      1.007  STO 00  CF 00  INT
006   LBL 00
        STO IND 00  2  3  FS?C 00  Clx  x>0?  SF 00
        +  *
016   ISG 00  GTO 00
018 END