Misez Rapide–Accélérez n°2 : La suite des 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 : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez Rapide–Accélérez n°2 : La suite des nombres de Hamming

Message par C.Ret » 30 sept. 2015 11:25

Image


Ce magnifique diagramme de Hass a l’inconvénient majeur de ne pas présenter les nombres de Hamming dans l’ordre.

Afin de perpétré la nouvelle rubrique des Misez Rapide – Accélérez, je vous propose, de mesurer les performances de nos vieux pockets et micro à la génération ordonnées 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 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

Un peu comme Dijkstra, Edsger W. l’avait fait en 1976 dans sont 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 de générer la séquence ordonnée de ces nombres sur nos Pockets et Micros préférés.

Evidemment, ce M.R.A. est en relation directe avec le M.P.O. n°67 qui partage le même thème. Mais, il n’en a pas le même objectif.

L’objectif de ce M.R.A. est de générer dans l’ordre et au plus vite la liste des nombres de Hamming.

Quel sera le temps mis par votre appareil pour afficher ou imprimer dans l’ordre les 10, 20, 50, 100, 200, 500 ou 1000 premiers nombre de Hammig ?

Votre technique permet-elle de déterminer en un temps raisonnable quel est le n-ième nombre de Hamming de la série.
Est-il possible de trouver le 1500ième, le 2000ième, le 5000ième , voir même le 10000ième ou le millionième ?


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 chaque entier en facteur premiers et les afficher/imprimer au fur et à mesure,
  • construire par récurrence l’ensemble H des nombres de Hamming, sachant que si H est un ensemble composé uniquement de nombre 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 parcourir les gammes diatoniques afin d’en lister les harmoniques,
  • retrouver les plaquettes d’argile que votre grand-père archéologue a remmenée d’Asie sumérienne et comprendre sont système de classement afin de remettre dans l’ordre les glyphes mésopotamiens qui y sont gravées,
  • tirer au sort le résultat du programme,…
  • Utiliser les résultats du MPO n°67
  • utiliser un algorithme personnel, mais fort dynamique...
Le chronométrage du programme pourra se faire en interne ou à l’aide d’un chronographe externe comme pour le MRA précédant. Dans ce dernier cas, un signal sonore facilitera la mesure de la performance.

Afficher ou imprimer de longues listes prends du temps et consomme des ressources. Afin de faciliter l’évaluation nous ne mesurerons les temps d’affichage/impression que pour les listes contenant moins de 50 nombres.

A partir de 100 nombres, nous ne mesurerons que le temps déterminé pour trouver le n-ième élément de la série. Ce qui sera plus rapide et plus économique. Bien entendu, cela sous-entend que le programme testé est capable de déterminer tous les éléments de la série quelque soit leur coordonnée et qu’il n’y a pas de « trou ».


Quelque soit l’algorithme que vous déciderez d’implémenter dans votre calculette ou micro, n’oubliez pas de Miser Rapide et d’Accélérer.
Dernière édition par C.Ret le 30 sept. 2015 15:19, édité 1 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez Rapide–Accéléré n°2 : La suite des nombres de Hamm

Message par caloubugs » 30 sept. 2015 11:50

C.Ret a écrit :[img
[*]trouver les intonations justes de votre instrument de musique préféré et parcourir les gammes diatoniques afin d’en lister les harmoniques,
[*]retrouver les plaquettes d’argile que votre grand-père archéologue a remmenée d’Asie sumérienne et comprendre sont système de classement afin de remettre dans l’ordre les glyphes mésopotamiens qui y sont gravées,
[*]tirer au sort le résultat du programme,…
:mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen: :mrgreen:

Pour les plaquettes d'argile, je prends, sauf si les piles ont coulé... :arrow:

Sinon, merci de continuer la route des MRA, le challenge est sympa !

Pour les comparaisons, je pense que l'on peut partir sur la détermination du 100e, 200e, 500e, etc... Ca permettra de faire de jolis tableaux !
Ca limite l'impact de l'affichage qui peut être très différent d'une machine à l'autre...
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par caloubugs » 30 sept. 2015 21:37

Allez hop, un premier prog qui je pense va s'optimiser grave.

Pb, déjà pour atteindre le 100e nombre de hamming (1536), il a fallu 160,93 s sur l'émulateur de la 71B (suis pas chez moi là).

Voilou le code :

Code : Tout sélectionner

5 M=0 @ K=0
10 INPUT I @ T=TIME
20 M=M+1 @ N=M @ GOSUB100 @ IF N>1 THEN 20 ELSE K=K+1
30 IF K<I THEN 20
40 DISP M;TIME-T
50 END
100 IF NOT MOD(N,2) THEN N=N/2 @ GOTO 100
110 IF NOT MOD(N,3) THEN N=N/3 @ GOTO 110
120 IF NOT MOD(N,5) THEN N=N/5 @ GOTO 120
130 RETURN
Va falloir se pencher sur ça, c'est pas génial pour le moment et j'avoue avoir du mal avec le code RPL de nos compères qui se sont déjà essayés sur le MPO :|
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par caloubugs » 30 sept. 2015 23:59

Une première petite optimisation du code, sans le Gosub qui mange du cycle horloge, maintenant le 100e hamming est atteint en 157,59s (3s de gagnées, incroyable :mrgreen: )

Code : Tout sélectionner

5 M=0 @ K=0
10 INPUT I @ T=TIME
20 M=M+1 @ N=M @ GOSUB100 @ 
30 IF NOT MOD(N,2) THEN N=N/2 @ GOTO 30
40 IF NOT MOD(N,3) THEN N=N/3 @ GOTO 40
50 IF NOT MOD(N,5) THEN N=N/5 @ GOTO 50
60 IF N>1 THEN 20 ELSE K=K+1
70 IF K<I THEN 20
80 DISP M;TIME-T
Malgré tout, pour gagner de la performance, va falloir trouver une astuce plus mathématique. La force brute, pas terrible.
D'autant plus que le 250e est 38880 (ça veut bien dire qu'on teste une grande majorité de nombres qui ne risquent pas d'être des candidats)...
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6932
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par gege » 01 oct. 2015 00:28

Bonjour,
La théorie semble complexe, Internet livre quelques pépites (INRIA...) mais bobo la tête !
G.E.

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par Marge » 01 oct. 2015 02:14

Je ne suis pas mathématicien, mais je pense que cela peut être résolu par une approche graphique en 3D : matricielle ? observez le diagramme à la perspective inversée !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
Pocket
Administrateur
Administrateur
Messages : 5638
Inscription : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par Pocket » 01 oct. 2015 08:52

Salut,

Ou une approche en arbre (à mon avis plus facile, mais je n'ai pas creusé).

A+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image

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

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par bernouilli92 » 01 oct. 2015 10:33

Si on prend un repère en trois dimensions (0,i,j,k) avec comme vecteur unitaires (0,i)=2 (O,j)=3 et (O,k)=5, les nombres de hamming peuvent être placés sur les points ayant des coordonnées positives.
C'est illustré par l'image du post initial.
HP, Casio, Sharp, Psion, quelques TI et divers autres

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par caloubugs » 01 oct. 2015 10:54

L'approche en 3D est sympathique visuellement, mais après, faut quand même arriver à classer les nombres dans l'ordre...
Et avec des nombres répartis dans l'espace, là je suis d'accord, bobo aux neurones... 8O
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...

Avatar de l’utilisateur
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4411
Inscription : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par charognard » 01 oct. 2015 12:31

Sur G850V
ça sort la liste triée de la suite jusqu'à 159 (Dans S)

Temps : 118s en Basic

Code : Tout sélectionner

10  CLS
20  FOR A=0 TO 12
30       FOR B=0 TO 8
40            FOR C=0 TO 5
50                 D=2^A*3^B*5^C-1
60                 IF D<6912 THEN PSET (D MOD 144, D/144)
70            NEXT C
80       NEXT B
90  NEXT A
100 DIM S(160)
140 I=1
150 FOR Y=0 TO 47
160      FOR X=0 TO 143
170           IF POINT (X,Y) LET S(I)=X+1+Y*144,I=I+1
180      NEXT X
190 NEXT Y
Exemple :
S(100) = 1536
Dernière édition par charognard le 01 oct. 2015 13:04, édité 3 fois.

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par caloubugs » 01 oct. 2015 12:42

charognard a écrit :Sur G850V
ça sort la liste triée de la suite jusqu'à 159 (Dans S)

Code : Tout sélectionner

10  CLS
20  FOR A=0 TO 12
30       FOR B=0 TO 8
40            FOR C=0 TO 5
50                 D=2^A*3^B*5^C-1
60                 IF D<6912 THEN PSET (D MOD 144, D/144)
70            NEXT C
80       NEXT B
90  NEXT A
100 DIM S(160)
140 I=1
150 FOR Y=0 TO 47
160      FOR X=0 TO 143
170           IF POINT (X,Y) LET A (I)=X+1+Y*144,I=I+1
180      NEXT X
190 NEXT Y
Exemple :
S(100) = 1536
J'aurais jamais pensé faire un tri en profitant des possibilités graphiques de ma machine...
Astucieux !
Du coup, ça doit aller assez vite non ? (la bécane doit déjà l'être à la base...)
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...

Avatar de l’utilisateur
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4411
Inscription : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par charognard » 01 oct. 2015 12:58

En basic pas de trop 118s pour 159 termes triés.
Mais en C ça doit aller au moins 2x plus vite. Et je ne te parle même pas en MIX C assembleur (la 2eme partie deL'algo s'y prête)

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

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par bernouilli92 » 01 oct. 2015 13:06

caloubugs a écrit :L'approche en 3D est sympathique visuellement, mais après, faut quand même arriver à classer les nombres dans l'ordre...
Et avec des nombres répartis dans l'espace, là je suis d'accord, bobo aux neurones... 8O
C'est bien là la difficulté de cet exercice, il faut forcément que les nombres soient triés pour pouvoir avoir le Nième.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4411
Inscription : 06 juin 2007 19:28
Localisation : Indre et loire
Contact :

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par charognard » 01 oct. 2015 13:10

bernouilli92 a écrit :
caloubugs a écrit :L'approche en 3D est sympathique visuellement, mais après, faut quand même arriver à classer les nombres dans l'ordre...
Et avec des nombres répartis dans l'espace, là je suis d'accord, bobo aux neurones... 8O
C'est bien là la difficulté de cet exercice, il faut forcément que les nombres soient triés pour pouvoir avoir le Nième.
Les miens sont triés ;)

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5221
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham

Message par Marge » 01 oct. 2015 13:21

En fait, le diagramme présente bien les nombres dans l'ordre vertical (bas->haut) selon une échelle logarithmique sur un plan.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

Répondre

Revenir vers « Tous les Pockets »