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 du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 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 »

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.
Modifié en dernier par C.Ret le 30 sept. 2015 15:19, modifié 1 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.
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 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 »

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 : 434
Enregistré le : 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 »

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 : 434
Enregistré le : 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 »

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 du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

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

Message par gege »

Bonjour,
La théorie semble complexe, Internet livre quelques pépites (INRIA...) mais bobo la tête !
G.E.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 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 »

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 !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5941
Enregistré le : 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 »

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 du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5229
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

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 : 434
Enregistré le : 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 »

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 du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 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 »

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
Modifié en dernier par charognard le 01 oct. 2015 13:04, modifié 3 fois.
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 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 »

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 du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 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 »

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 du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5229
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

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 du membre
charognard
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4412
Enregistré le : 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 »

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 du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 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 »

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 !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Répondre

Retourner vers « Tous les Pockets »