M.P.O. n°67 : Les nombres de Hamming

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

Répondre
Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1912
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

M.P.O. n°67 : Les nombres de Hamming

Message par C.Ret » 30 sept. 2015 10:53

Image


Comme vous l’aurez compris en observant ce magnifique diagramme de Hass, le thème de ce nouvel M.P.O. vous propose de s'attarder sur l’étude des nombres de Hamming. Les nombres de Hamming ont plusieurs dénominations ; en fonction de leur champ d’application se sont des nombres moches , des nombres cinq-mous ou de glyphes babyloniens.


Les mathèmatiques les définissent comme étant les entiers de la forme Image, c'est-à-dire les entiers dont les seuls diviseurs premiers sont 2, 3 ou 5.

Les 20 premiers Nombre de Hamming sont : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36


Comme Dijkstra, Edsger W. l’avait fait en 1976 dans son ouvrage A Discipline of Programming au chapitre n°17 intitulé "An exercise attributed to R. W. Hamming" ( Prentice-Hall, pp. 129–134, ISBN 978-0132158718 ), je vous propose quelque exercice pour vos Pockets et Micros préférés.

Evidemment, ce M.P.O. est en relation directe avec le M.R.A. n°2 qui partage le même thème mais pas le même objectif.


L’objectif de ce M.P.O. est d’écrire un code pour votre calculette ou micro qui permet de vérifier qu’un entier donné N est effectivement un nombre de Hamming.

Vous pourrez pour cela mettre en œuvre tout algorithme de votre choix et de votre convenance qui utilisera ou non les multiples propriétés des Nombre de Hamming.

Vous pourriez utiliser, par exemple, l’une ou l’autre des méthodes suivantes:
  • décomposer le nombre N en facteur premiers et vérfier qu’il n’en a pas d’autres que 2,3 et 5 ;
  • rechercher par récurrence l’entier N dans l’ensemble H des nombre de Hamming, sachant que si H est un ensemble composé uniquement de nombres de Hamming, alors 2.H, 3.H et 5.H sont également des ensembles de nombres de Hamming
  • trouver les intonations justes de votre instrument de musique préféré et vérifier que N fait bien partie d’une harmonique de la gamme diatonique,
  • retrouver les plaquettes d’argile que votre grand-père archéologue a remmenée d’Asie sumérienne et retrouver N parmi les glyphes mésopotamiens,
  • tirer au sort le résultat du programme,… ou utiliser les résultats du MRA n°2
  • utiliser un algorithme personnel, mais fort sympathique...
Le programme n’a pas d’autre contrainte que d’indiquer si le nombre saisi est un Nombre de Hamming ou Non et cela par tout moyen que vous jugerez opportun en fonction des capacités d’affichage, d’impression, la présence d’un signal sonore, d’un clignotement, de drapeaux, d'une couleur, de vibrations, explosions, ou la désintégration … de votre calculateur.


Quelques exemples de nombres à tester :

Code : Tout sélectionner

 Ne sont pas des nombres de Hamming:

       123 =  1 x 3 x 41 

                   4    2
      5040 =  1 x 2  x 3  x 5 x 7

                   4    2
 337689200 =  1 x 2  x 5  x 31 x 113 x 241


Sont des Nombres de Hamming:

                   4    2
       720 =  1 x 2  x 3  x 5 

                   11    7    3
 559872000 =  1 x 2   x 3  x 5  

                   10    5    5
 777600000 =  1 x 2   x 3  x 5  
Quelque soit l’algorithme que vous déciderez d’implémenter dans votre calculette ou micro, n’oublier pas de Miser Petit et d’Optimiser.
Dernière édition par C.Ret le 23 sept. 2017 18:20, édité 1 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator
Sommaire des M.P.O.s

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4502
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: M.P.O. n°67 : Les nombres de Hamming

Message par bernouilli92 » 30 sept. 2015 15:20

Voici ma version pour hp 28 et hp 48 :

Code : Tout sélectionner

« 5
  WHILE DUP 1 >
  REPEAT
    WHILE DUP2 MOD NOT
    REPEAT 
      SWAP OVER / 
      SWAP
    END 
    .7 * IP
  END 
  DROP 1 ==
»
Taille: 85,5 octets


Et une version pour hp 42 basée sur le même principe :

Code : Tout sélectionner

01 LBL "Hamming"
02 STO 00
03 5
04 STO 01
05 LBL 01
06 RCL 00
07 RCL 01
08 MOD
09 x≠0?
10 GTO 02
11 RCL 01
12 STO÷ 00
13 GTO 01
14 LBL 02
15 RCL 01
16 0.7
17 *
18 IP
19 STO 01
20 1
21 X<>Y?
22 GTO 01
23 RCL 00
24 1
25 X≠Y?
26 0
27 END
Je ne suis toujours pas familier avec le langage de programmation des hp41/42.

Et une autre légèrement plus courte en utilisant un sous-programme et en remplaçant le test final par 1/X IP:

Code : Tout sélectionner

01 LBL "Hamming"
02 STO 00
03 5
04 XEQ 03
05 3 
06 XEQ 03
07 2
08 XEQ 03
09 RCL 00
10 1/X
11 IP
12 RTN
13 LBL 03
14 STO 01
15 LBL 01
16 RCL 00
17 RCL 01
18 MOD
19 x≠0?
20 RTN
21 RCL 01
22 STO÷ 00
23 GTO 01
24 END
Edit :
On peut gagner 8 octets sur la version RPL en remplaçant 0.7 * IP par 2 / CEIL

Code : Tout sélectionner

« 5
  WHILE DUP 1 >
  REPEAT
    WHILE DUP2 MOD NOT
    REPEAT 
      SWAP OVER / 
      SWAP
    END 
    2 / CEIL
  END 
  DROP 1 ==
»
Taille : 77,5 octets
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
babaorhum
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 581
Inscription : 13 janv. 2013 20:44
Localisation : Toulon-ouest

Re: M.P.O. n°67 : Les nombres de Hamming

Message par babaorhum » 30 sept. 2015 21:14

Bonjour,
En mode "boeuf" (sans réfléchir), 5 lignes sur mon sharp pc-1350 :

Code : Tout sélectionner

10 "H" AREAD N : D=5 : GOSUB 40 : D=3 :GOSUB 40 : D=2 : GOSUB 40
20 IF N=1 THEN PRINT "YES" : END 
30 PRINT "NO" : END 
40 M=N/D : IF M=INT M THEN LET N=M : GOTO  40
50 RETURN 
33768900 def H donne "NO"
559872000 def H donne "YES"

... Pas calculé le nombre d'octets (il y a d'autres trucs en mémoire. .)
BaBaoRhum
HP J728,200LX,1000CX,75C,71B, 48GX,42s,41CX,35s,32E,32Sii,28S,22s,21,16C,11C,12Cp
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,850P,3900P,4000P
TI-74&92 ; Canon X-07 ; Panasonic HHC RL-H1400 ; TANDY EC-4026

alain1261
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 32
Inscription : 11 juil. 2015 00:28

Re: M.P.O. n°67 : Les nombres de Hamming

Message par alain1261 » 01 oct. 2015 08:53

babaorhum a écrit :Bonjour,
En mode "boeuf" (sans réfléchir), 5 lignes sur mon sharp pc-1350 :

Code : Tout sélectionner

10 "H" AREAD N : D=5 : GOSUB 40 : D=3 :GOSUB 40 : D=2 : GOSUB 40
20 IF N=1 THEN PRINT "YES" : END 
30 PRINT "NO" : END 
40 M=N/D : IF M=INT M THEN LET N=M : GOTO  40
50 RETURN 
33768900 def H donne "NO"
559872000 def H donne "YES"

... Pas calculé le nombre d'octets (il y a d'autres trucs en mémoire. .)
Simple mais efficace.

Bien vu pour le INT sans les parenthèses.

Sur mon PC1261, ton programme consomme 90 octets.
Mon parcours : TI30 -> F-73 -> PC1261 -> PC1475 ... -> TI92 -> Voyage 200 -> ... ?
Collection de calculatrices à LED (Casio FX-19, CBM SR36, HP25, HP33E, HP67, TI58C, ...) plus quelques références (PC1211, HP41CV, ...)

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1912
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: M.P.O. n°67 : Les nombres de Hamming

Message par C.Ret » 01 oct. 2015 18:52

Ah! Je vois avec satisfaction que les premiers codes apparaissent.

A priori, vous utilisez surtout l'approche par la décomposition en facteur.
C'est effectivement une voie possible.

J'ai moi aussi quelques trucs dans ce genre de détermination :

Code : Tout sélectionner

dload"hamming test"

searching for 0:hamming test
loading
ready.
list

10 input "[dwn][dwn]N=";n  : print "[up]"chr$(27)"q"n; : s$="="
20 if n>1 then f%=2:gosub 1000:f%=3:gosub 1000:f%=5:gosub 1000
30 if n=1 then print " is hamming" : else print s$;n
40 end
1000 p%=0
1010 q=n/f%:if q=int(q) then p%=p%+1:n=q:goto 1010
1020 if p% then print s$;f%;:s$=".":if p%>1 then print "[up][lft][lft]";p%;"[lft][dwn]";
1030 return

ready.
RUN


 123 = 3 . 41

         4   2
 5040 = 2 . 3 . 5 . 7

              4   2
 337689200 = 2 . 5 . 844223

        4   2
 720 = 2 . 3 . 5  is hamming

              11   7   3
 559872000 = 2  . 3 . 5  is hamming

              10   5   5
 777600000 = 2  . 3 . 5  is hamming


N=? _




Tant qu'à décomposer, autant en profiter pour afficher la décomposition.

En RPL, j'avais pensé à une astuce récurrente.
N est un entier de Hamming ayant pour base (2,3,5) si l'un au moins des nombres H/2, H/3 ou H/5 est aussi un entier de hamming issue de la base(2,3,5).

Ce qui revient à décomposé jusqu'à arriver à 1 :

Code : Tout sélectionner

21600   
   /2 /2 /2 /2 /2 --> 675
                    /5 /5 ---> 27
                          /3 /3  /3  --->1  donc 21600 est hamming 21600 = 2^5.3^3.5^2

ISHAM?:
« IF DUP 1 == THEN DROP "is Hamming" KILL
  ELSE IF  DUP  2  MOD  NOT  THEN 2  /  ISHAM?
     ELSE IF  DUP 3  MOD  NOT  THEN  3 / ISHAM?
       ELSE IF DUP 5 MOD NOT THEN 5 / ISHAM? 
            END
       END
     END
  END »
Mais c'est pas rapide et rempli la pile de nombres... sans compter que la récurrence consomme un max de mémoire à cause des centaines d'appels de la fonction ISHAM?

Donc, j'ai ensuite trouvé plus facile de décomposer comme le fait bernouilli92
Mais pour fair court, j'utilise une structure FOR / NEXT, quitte à tester la multiplicité avec 4, ce qui est inutile (et toujours négatif car on vient d'épuiser celle de 2).
C'est un M.P.O., seul le nombre de pas compte, pas l'efficacité ou la vitesse ! :D

Code : Tout sélectionner

HAM?:
« 2 5 FOR f
     WHILE DUP f MOD NOT 
        REPEAT f / END
  NEXT 1 == »
ce qui en BASIC revient à faire :

Code : Tout sélectionner

10:"H" AREAD N : FOR F=2 TO 5 
20 IF (N MOD F) = 0  THEN N=N/F : GOTO 20
30 NEXT F: PRINT N=1 : END


Mais pour mon HP41C et mon très lent SHARP PC-1211, j'ai trouvé bien mieux en recherchant du côté de la Mésopotamie antique.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator
Sommaire des M.P.O.s

Avatar de l’utilisateur
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6072
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: M.P.O. n°67 : Les nombres de Hamming

Message par ledudu » 23 janv. 2017 00:33

Machine : Casio Pro FX-1
Langage : Fortran Casio

Ce petit problème correspond tout juste aux capacités de cette machine.

Soit N=(2^a) x (3^b) x (5^c) x reste

Les registres 4, 5 et 6 contiennent les diviseurs 2, 3 et 5.
Les registres 7, 8 et 9 conservent le nombre de facteurs : a,b et c.

Le registre I sert de référence indirecte.
Si I=4 alors IM pointe sur le registre 4 et vaut donc 2.
Pour I=4, on cumule a dans le registre 7, puis pour I=5, b dans le registre 8 et enfin pour I=6, c dans le registre 9.

On START et on entre le nombre cible sur ENT 1.

A la fin des calculs, la machine affiche d'abord le reste, puis le nombre de puissances de 2, de 3 puis de 5. Il faut appuyer sur ANS pour afficher le nombre suivant.

Remarque : 3=2+0-0 : calcul de la partie entière du registre 2 dans le registre 3 grâce au registre 0 qui vaut 10^10 et à l'arrondi fait par la machine.

Code : Tout sélectionner

ENT 1:0=K10 10^x:4=K2:5=K3:6=K5:I=K4:
ST #1:2=1/IM:3=2+0-0:IF 3=2:3:2:3:
ST #2:1=2:I=I+5:IM=IM+K1:I=I-5:GOTO 1:
ST #3:IF I=K6:4:5:4:
ST #4:I=I+K1:GOTO 1:
ST #5:ANS 1:7:8:9:
127 pas / 127
D'autres programmes pour PRO Fx-1.

Gilles59
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 1129
Inscription : 27 oct. 2010 20:46

Re: M.P.O. n°67 : Les nombres de Hamming

Message par Gilles59 » 16 juil. 2017 22:22

Bonjour à tous.

Sur 50G c'est un peu de la triche, en plus avec l'indispensable Library GOFERLIST

Code : Tout sélectionner

<< FACTORS  << TYPE >> Filter  { 5 3 2 } SAME >>
Instantané sur la vraie calc.
Casio FX-502P /602P / 603P/ FX180P+ / FX4000P / TI66 / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49G+ / 50G / HP Prime / Amstrad CPC 6128+

Répondre

Revenir vers « Tous les Pockets »

Qui est en ligne ?

Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 56 invités