Misez p'tit Optimisez n°100 : Quand le 0 devient backspace

[C.Ret]

Je me demandais si une variation en binaire serait amusante, par exemple entrer 123 et la machine sort 3 car :

123 = 10011001110 b --> MPO100 --> 11 b = 3

Déjà fait ! Aucun intérêt pour une HP-28S avec le code posté précédemment:
BIN #10011001110b MPO100 renvoie #11b puis une pression sur B→R affiche 3.

Par contre,
« HEX #100000000010011b MPO100 B→R » renvoie 19.
et je vous laisserai m'expliquer pourquoi !

[Schraf]

Je pensais à des versions utilisant les opérateurs logiques AND, XOR, décalage de bits etc.

Par contre, je comprends bien le 10011001110b = 4013h --> MPO100 --> 13h = 19 mais pour moi la réponse serait 10011001110b = 11b = 3

Mais ça revient à compter le nombre de 1 initiaux - le nombre de 0 et donc ça rappelle le MPO n°96 !!

[C.Ret]

Oui, je me suis rendu compte de mon erreur lors du premier essai, j'avais laissé mon HP-28S en mode HEXadécimal et donc l'exemple binaire ne fonctionnait pas. L'instruction →STR utilise le mode en cours, indépendant de la base saisie (= le petit b )

Bon, le MPO 96 me rappelle l'avantage de l' HP-16C et de sa fonction #B

En attendant que quelqu'un trouve une solution à base de OR XOR AND et NOT logiques, je vous donne ma version numérique (en base 10 habituelle) pour une HP-15C :

MPO100 - HP15C.gif (10.57 Kio) Vu 4583 fois

(Par souci d'économie je n'ai pas mis de label initial ni de RTN final - mais rien ne vous empêche de le faire ).

Ce code va pouvoir servir de base pour les HP Classic, Woodstocks et autres Spices ...
... quoi qu'à bien y penser la conversion des ISG/DSE en ISZ/DSZ n'est peut-être pas immédiate (sauf pour Marge certainement).

Et aussi un moyen de raccourcir considérablement le code pour les Coconuts et Halfnuts !

[bernouilli92]

Voici une version pour hp48 utilisant les chaînes de caractères :

Code : Tout sélectionner

« →STR 
  → S
  « 0 1 S SIZE
    FOR I 
      S I DUP SUB STR→
      IF DUP
      THEN 
        SWAP 10 * +
      ELSE 
        DROP 10 / IP
      END
    NEXT
  »
»

Et la même version mais en python :

Code : Tout sélectionner

def mpo100(n):
  s=0
  for c in str(n):
    s=10*s+int(c) if c!='0' else s//10
  return s
  
print mpo100(15607008)

[Schraf]

En parcourant le manuel du HP 48G, je tombe sur STREAM :

STREAM

HP48.jpg (100.03 Kio) Vu 4524 fois

Imaginons que les chiffres soient donnés sous la forme d'une liste, par exemple {1 5 6 0 7 0 0 8}, la machine prend les 2 premiers termes (X=1 et Y=5) et exécute l'opération, dans notre cas il faut obtenir 15 (1*10+5), on recommence avec 15 et 6 pour obtenir 156 (15*10+6). Ensuite, avec 156 et 0, on doit arriver à 15 (suppression du 6, ce qui revient à ent(156 / 10)) etc. Finalement, ça donne :

• Si Y <> 0 alors X = X * 10 + Y ( = ENT(X * 10 + Y))

• Si Y == 0 alors X = ENT(X / 10) ( = ENT(X / 10 + 0))

D'où une formule unique : X = ENT(X # 10 + Y) où # est * si Y <> 0 et / sinon.

Quelqu'un sait comment on pourrait écrire sur HP 48 quelque chose comme : << X 10 (* ou /) Y + IP >> ?

En Python ça pourrait donner :

Code : Tout sélectionner

def mpo(l):
  s = 0
  for v in l:
    s = int(eval(str(s) + "/*"[v>0] + "10") + v)
  return s 

[bernouilli92]

Tu peux utiliser ce programme avec STREAM, c’est ce qu’il y a dans mon programme précédent :

Code : Tout sélectionner

«
  IF DUP
  THEN SWAP 10 * +
  ELSE DROP 10 / IP
  END
»

Ou, pour reprendre ta logique :

Code : Tout sélectionner

« → N
  « 10
    IF N
    THEN *
    ELSE /
    END N + IP
  »
»

Ou encore en n’utilisant pas de variable locale (c’est aussi le plus court des 3) :

Code : Tout sélectionner

« SWAP 10
  IF 3 PICK
  THEN *
  ELSE /
  END + IP
»

On peut aussi le stocker dans une variable, disons P100 et exécuter : { 1 2 0 5 6 0 0 9 } 'P100' STREAM
On obtient 19

[Schraf]

Ah effectivement, c'est bien pratique !

J'ai cependant une incompréhension avec la 2e version et, à mon avis, il y a un problème avec la 3e version :

Pour la première version : (exemple avec { 1 2 0 5 6 0 0 9 })

STREAM met Y = 1, X = 2 dans la pile
Comme 2 n'est pas nul, on inverse X et Y, on ajoute 10 dans la pile : Z = 2, Y = 1, X = 10
On fait le produit XY puis la somme X+Y et on obtient 12
A l'étape suivante STREAM ajoute 0 à la pile : Y = 12, X = 0
Dans ce cas on élimine (DROP) le X, on ajoute 10 dans la pile : Y = 12, X = 10
Puis division et partie entière : X = 1
Tout est OK

Pour la seconde version :

Je n'arrive pas à utiliser PRG - RUN - DBUG pour suivre pas à pas le programme (à cause du STREAM) donc je ne sais pas si N récupère le résultat précédent ou le nouvel élément de la liste (le résultat précédent étant mis dans Y)

Dans les 2 cas je bloque :

STREAM met Y = 1, X = 2
Imaginons que 2 → N (nouvel élément de la liste)
Ajout de 10 dans la pile Z = 1, Y = 2, X = 10
IF ajoute le résultat dans la pile mais THEN l'enlève, donc sauf erreur de ma part, rien ne bouge...
Comme N n'est pas nul, on fait * puis "+N" ce qui devrait faire 22 or la machine affiche bien 12

Si maintenant STREAM met Y = 1, X = 2
Imaginons que 1 → N (résultat précédent, qui doit être j'imagine la première valeur de la liste)
Ajout de 10 dans la pile Z = 1, Y = 2, X = 10
Comme N n'est pas nul, on fait * puis "+N" ce qui devrait faire 21

Donc je n'arrive pas à suivre la logique du processus...

Pour la 3e version :

Avec SWAP & 10 & PICK on aura 2 | 1 | Y = 10 | X = 2 dans la pile
Comme 2 n'est pas nul, on fait 10 * 2 et ensuite + 1 soit 21
Et effectivement, c'est ce qu'indique la machine. Or ça devrait être 12
Bon là je crois que c'est la version qui ne va pas

[Schraf]

Voici une proposition en Python pour la version binaire (Rappel : par exemple 14 = 1110b --> MPO100 --> 11b = 3). J'ai utilisé << et >> au lieu des multiplications et divisions par 2 et l'opérateur & pour tester l'unité :

Code : Tout sélectionner

def mpobin(n):
  s = z = 0
  while n > 0:
    if 1 & n:
      if z: z -= 1
      else : s = 1 + (s << 1)
    else: z += 1
    n >>= 1
  return s

On peut ajouter un print('{:>10}{:>26}{:>13}{:>2}'.format(n,bin(n),bin(s),z)) après le while pour voir plus précisément le déroulement :

Code : Tout sélectionner

>> mpobin(14)
        14                    0b1110          0b0 0
         7                     0b111          0b0 1
         3                      0b11          0b0 0
         1                       0b1          0b1 0
3

Code : Tout sélectionner

>> mpobin(3141592)
   3141592  0b1011111110111111011000          0b0 0
   1570796   0b101111111011111101100          0b0 1
    785398    0b10111111101111110110          0b0 2
    392699     0b1011111110111111011          0b0 3
    196349      0b101111111011111101          0b0 2
     98174       0b10111111101111110          0b0 1
     49087        0b1011111110111111          0b0 2
     24543         0b101111111011111          0b0 1
     12271          0b10111111101111          0b0 0
      6135           0b1011111110111          0b1 0
      3067            0b101111111011         0b11 0
      1533             0b10111111101        0b111 0
       766              0b1011111110       0b1111 0
       383               0b101111111       0b1111 1
       191                0b10111111       0b1111 0
        95                 0b1011111      0b11111 0
        47                  0b101111     0b111111 0
        23                   0b10111    0b1111111 0
        11                    0b1011   0b11111111 0
         5                     0b101  0b111111111 0
         2                      0b10 0b1111111111 0
         1                       0b1 0b1111111111 1
1023

[bernouilli92]

Pour la seconde version :

Je n'arrive pas à utiliser PRG - RUN - DBUG pour suivre pas à pas le programme (à cause du STREAM) donc je ne sais pas si N récupère le résultat précédent ou le nouvel élément de la liste (le résultat précédent étant mis dans Y)

Tu peux débugger le programme en le lançant avec DBUG et en mettant les bons paramètres dans la pile : avec 12 et 3 tu dois obtenir 123 et avec 12 et 0, tu dois obtenir 1.

STREAM met Y = 1, X = 2
Imaginons que 2 → N (nouvel élément de la liste)
Ajout de 10 dans la pile Z = 1, Y = 2, X = 10
IF ajoute le résultat dans la pile mais THEN l'enlève, donc sauf erreur de ma part, rien ne bouge...
Comme N n'est pas nul, on fait * puis "+N" ce qui devrait faire 22 or la machine affiche bien 12

Si maintenant STREAM met Y = 1, X = 2
Imaginons que 1 → N (résultat précédent, qui doit être j'imagine la première valeur de la liste)
Ajout de 10 dans la pile Z = 1, Y = 2, X = 10
Comme N n'est pas nul, on fait * puis "+N" ce qui devrait faire 21

Donc je n'arrive pas à suivre la logique du processus...

Dans un IF THEN, le IF ne fait rien du tout, c’est le THEN qui enlève un élément de la pile.
IF N THEN peut aussi s’écrire N IF THEN
Ici c’est la valeur de N qui est testée et qui donc est enlevée de la pile au THEN ou ELSE.
Ensuite le -> N enlève un élément dans la pile et le met dans N
Donc après le -> N la pile ne contient plus que 1 et N contient 2. On rajoute 10 dans la pile, on multiplie, ce qui donne 10 et on rajoute N ce qui fait 12.

Pour la 3e version :

Avec SWAP & 10 & PICK on aura 2 | 1 | Y = 10 | X = 2 dans la pile
Comme 2 n'est pas nul, on fait 10 * 2 et ensuite + 1 soit 21
Et effectivement, c'est ce qu'indique la machine. Or ça devrait être 12
Bon là je crois que c'est la version qui ne va pas

Au moment du test, 2 est enlevé de la pile, il reste 2 | 1 | 10, la multiplication donne 2 | 10 et l’addition donne 12.

[Schraf]

Merci bernoulli92 pour ces précisions, je vais reprendre tout ça tranquillement, quand j'écrivais que le IF mettait qq chose dans la pile, je pensais au test et que le THEN l'enlevait juste après et donc finalement que rien ne bougeait. Mais faut que je vois ça mieux.

Ci-dessous une traduction possible (de la version binaire) pour la HP WP 34S. J'ai peut-être abusé des SKIP (qui permettent de faire des sauts en avant d'un certain nombre de pas (BACK faisant la même chose en arrière)).

Code : Tout sélectionner

001 LBL A
002 FILL		; J'ai repris l'astuce de zpalm du MPO53
003 STO- Y		; Y = 0 (Nombre actuel de 0)
004 STO- Z		; Z = 0 (Résultat final)
005 x=0?		; Fin ?
006 SKIP 018
007 EVEN?		; N pair ? = se termine par 0 en binaire
008 SKIP 011		; Dans ce cas aller au pas 020
009 x[<->] Y		; On met le nombre de 0 au niveau X de la pile
010 x[!=]0?		; Y avait-il déjà des 0 ?
011 SKIP 005		; Un 0 supprime le 1 actuel et donc le nb de 0 va diminuer de 1 (pas 017)
012 2			; Le résultat final est maintenant au niveau de T
013 STO[times] T	; 2 * T + 1 --> T
014 INC T
015 DROP		; On enlève le 2
016 SKIP 001		; Le nombre de 0 ne doit pas diminuer
017 DEC X		; Le nombre de 0 doit diminuer de 1
018 x[<->] Y		; On remet les éléments dans l'ordre initial
019 SKIP 001		; Comme le nombre se finissait par 1, le nombre de 0 ne doit pas augmenter
020 INC Y		; Si le nombre est pair, on ajoute +1 au nombre de 0
021 2			; Dans tous les cas on fait...
022 /			; ENT(N / 2) --> N
023 IP
024 BACK 019		; Retour à la ligne 005
025 RCL Z		; Affichage du résultat
026 END

• 14 A donne 3

• 314159 A donne 1023

• 999,999,999,999 A donne 4095

Je disais dans un post précédent que je trouvais la machine réelle très rapide, mais avec les versions pour Android ou sur ordinateur, tous les résultats (Syracuse entre autres) sont immédiats...

[C.Ret]

Bon, je n'avais pas de STREAM sur mon HP-28S, j'en ai bricolé un rapide qui ne fonctionne que pour les fonctions dyadiques (qui prennent exactement deux arguments dans la pile et fonction car elles ne renvoient qu'un seul objet).

Du coup, si l'argument est sous forme de liste, on peut utiliser le code suivant :

Code : Tout sélectionner

{1 5 6 0 7 0 0 8}
 « 10 OVER NOT « INV » IFT ROT * + IP »
STREAM

Le principe est d'inverser (ou non) le 10 afin que la multiplication qui suit soit en fait une division (ou non).

Je ne suis pas sûr que la structure . « ... » IFT prenne effectivement moins d'octets qu'une struture IF . THEN ... END classique qui serait :

Code : Tout sélectionner

{1 5 6 0 7 0 0 8}
 « 10 IF OVER NOT THEN INV END ROT * + IP »
STREAM 

Le ROT dans l'histoire est juste pour mettre dans le bon ordre les X et Y pour que l'on divise X et que l'on ajoute Y. Je ne sais pas si le STREAM des HP-48 fonctionne exactement comme mon bricolage !


Je donne pour info, et pour celles et ceux qui, comme moi, n'ont qu'une HP-28S et pas d'HP-48* ou HP-50g sous leurs doigts.

Code : Tout sélectionner

STREAM:
« → Fn2 « 2 OVER 1 GET WHILE ROT ROT DUP 1 ≠
                       REPEAT GETI 4 ROLL SWAP Fn2 EVAL END
          DROP2 » »

Vous constaterez qu'il n'y a pas de UNROT sur une HP-28S, d'où les ROT ROT
Le nom Fn2 de la variable locale et juste pour me souvenir que cette version ne fonctionne qu'avec une fonction dyadique.

[Schraf]

J'ai tenté une version en APL qui fonctionne mais qui devrait pouvoir être nettement optimisée. Je vais d'ailleurs suggérer cet exercice à Richard Park de chez Dyalog APL, il est très sympa et fait des trucs pas croyables.

Code : Tout sélectionner

MPO100 ← {~ 0 ∊ ⍵ : ⍵ ⋄ ∇⊃,/ (2 × 0 ∊¨ v) ↓¨ v ← (+\ 0 ≠ ⍵) ⊆ ⍵}

Explications avec u ← 1 5 6 0 7 0 0 8

Code : Tout sélectionner

     u ← 1 5 6 0 7 0 0 8

     0 ≠ u		⍝ Quel sont les éléments différents de 0
1 1 1 0 1 0 0 1
1 5 6 0 7 0 0 8

     +\ 0 ≠ u		⍝ Faire le balayage (Scan) avec l'opérateur +, c'est-à-dire ici une somme cumulée
1 2 3 3 4 4 4 5
1 5 6 0 7 0 0 8

   v ← (+\ 0 ≠ u) ⊆ u	⍝ Créer la partition ⊆ suivant (1) (2) (3 3) (4 4 4) (5) et mémoriser dans v
┌─┬─┬───┬─────┬─┐
│1│5│6 0│7 0 0│8│
└─┴─┴───┴─────┴─┘
 
    (2 × 0 ∊¨ v) ↓¨ v ← (+\ 0 ≠ u) ⊆ u 		⍝ Enlever pour chaque case (↓¨) soit 0 soit 2 termes suivant que 0 est dedans ∊ ou non 
┌─┬─┬┬─┬─┐
│1│5││0│8│
└─┴─┴┴─┴─┘

    ⊃,/(2 × 0 ∊¨ v) ↓¨ v ← (+\ 0 ≠ u) ⊆ u 	⍝ Joindre (,/) toutes les cases (il en reste donc qu'une) et prendre le premier élément ⊃ (donc le contenu)
1 5 0 8

~0∊⍵:⍵ ⋄ ∇... 		⍝ Si 0 n'est pas dans la liste, on a fini et on renvoie cette liste, sinon on applique l'algorithme à la nouvelle liste

      MPO100 u
1 8
      MPO100 9 0 0 0 0 0

      MPO100 2 0 0 3 3 0
3

Peut-être existe-t-il une solution avec seulement un scan...

[Gilles59]

En parcourant le manuel du HP 48G, je tombe sur STREAM :
HP48.jpg

A mon avis MAP ou DOSUB sont plus appropriés que STREAM mais je ne sais pas si elles existent sur la 48 (DOSUB l'est sauf sur les plus anciennes 48S et SX). L'idée , si l'entrée est une liste, peut être du genre :

Code : Tout sélectionner

<< IF THEN LASTARG ELSE DROP >> MAP 

(ou adapter avec DOSUB, il faut ajouter un paramètre 1 après ou avant la liste je ne sais plus). Ca retourne une liste qu'on peut facilement changer en chaine ou nombre
J'ai pas ma HP sous la main là.

[Gilles59]

J'ai tenté une version en APL qui fonctionne mais qui devrait pouvoir être nettement optimisée. Je vais d'ailleurs suggérer cet exercice à Richard Park de chez Dyalog APL, il est très sympa et fait des trucs pas croyables.

Code : Tout sélectionner

MPO100 ← {~ 0 ∊ ⍵ : ⍵ ⋄ ∇⊃,/ (2 × 0 ∊¨ v) ↓¨ v ← (+\ 0 ≠ ⍵) ⊆ ⍵}

Je n'y comprends rien mais c'est très beau. Vais essayer de comprendre avec tes explications, merci;D

[Schraf]

Bah voilà, un membre de l'équipe de Dyalog APL a trouvé une solution bien plus courte que la mienne

Code : Tout sélectionner

MPO100 ← {Φ ⊃ {0≡⍺:1↓⍵ ⋄ ⍺,⍵} / Φ⍵}

Ils ont repris l'idée du append et pop (Exemple avec u ← 1 5 6 0 7 0 0 8 )

Code : Tout sélectionner

      Φ 1 5 6 0 7 0 0 8		⍝ On inverse le vecteur
8 0 0 7 0 6 5 1

Lorsque l'on applique une réduction (/) à un vecteur V en utilisant une fonction f (l'expression entre {...}), le principe est :

f/ V signifie : (1er élément de V) f (2e élément de V) f ... f (dernier élément de V)

Et en APL les calculs se font toujours de la droite vers la gauche. ⍺ est le terme à gauche de f et ⍵ celui de droite.

Exemple :

Code : Tout sélectionner

{⍺,⍵,⍵}/ 1 2 3
 1 2 3 3 2 3 3 

Car à la première étape ⍺ = 2 et ⍵ = 3 (les 2 derniers termes du vecteur) et donc ⍺,⍵,⍵ = 2,3,3
A la seconde étape, ⍺ = 1 et ⍵ = 2,3,3, donc ⍺,⍵,⍵ = 1,2,3,3,2,3,3

Code : Tout sélectionner

{0≡⍺:1↓⍵ ⋄ ⍺,⍵}	⍝ Si le terme de gauche est nul on supprime le 1er élément de ⍵, sinon on les concatène

Avec 8 0 0 7 0 6 5 1 ça donne :

⍺ = 5 et ⍵ = 1 d'où la concaténation 5,1
⍺ = 6 et ⍵ = 5,1 d'où la concaténation 6,5,1
⍺ = 0 et ⍵ = 6,5,1 et comme ⍺ est nul on supprime le 1er élément de ⍵ ce qui fait 5,1
⍺ = 7 et ⍵ = 5,1 d'où la concaténation 7,5,1
⍺ = 0 et ⍵ = 7,5,1 d'où 5,1
⍺ = 0 et ⍵ = 5,1 d'où 1
⍺ = 8 et ⍵ = 1 d'où 8,1

Et à la fin on retourne (Φ) à nouveau le vecteur pour obtenir 1 8