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

Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5230
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 »

gege a écrit : Je suppose que tu es sur Palm 5mx ? Je testerai sur Sharp.
G.E.
non non, toujours sur C128.

@C-Ret : très très bien ton algo.
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 »

Oula, j'étais à mille lieues de partir sur des pointeurs. Quel algo en effet !

Et chapeau C.ret sur ta maîtrise de la police courrier pour présenter ces concepts. Mazette ! 8O

Ma réflexion en utilisant les listes était de considérer que la progression des nombres de Hamming est de type exponentiel et de se demander si entre par exemple 2^n et 2^(n+1), on n'a pas toujours un nombre limité de Hamming.
Ce qui permettrait alors de générer des listes limitées. Mais ça revient encore à calculer un nombre excessif et redondant de nombres candidats.

Le souci est bien la taille du buffer qu'on ne peut pas maitriser a priori : si l'objectif est de pouvoir sortir H(1000000)...

Sinon, n'étant pas à une humiliation près (et pour donner tort à bernouilli92 :mrgreen: ), je me suis amusé (pendant ma grippe intestinale du week-end, sympa) à comparer la méthode force brute (pas très forte d'ailleurs) avec celle que j'avais proposée en calculant H(n+1) à partir de H(n) (je l'appelle V2) :

Code Z-1GR pour la force brute

Code : Tout sélectionner

10 I=0:K=0:INPUT N:TIMER=0
20 I=I+1:M=I
30 IF M MOD 5=0 THEN M=M/5:GOTO30
40 IF M MOD 3=0 THEN M=M/3:GOTO40
50 IF M MOD 2=0 THEN M=M/2:GOTO50
60 IF M=1 THEN K=K+1 ELSE 20
70 IF K<N THEN 20
80 PRINT I,TIMER
Le code avec le calcul progressif de H(n) sans listes (meilleur pour le MPO d'ailleurs ! :tongue: ) :

Code : Tout sélectionner

10 INPUT I:TIMER=0:L2=LN2:L=1:FOR K=2 TO I:T=1:V=L
20 U=1
30 S=U*T:W=2^INT(LN(L/S)/L2+1):IF W<1 THEN W=1
40 R=W*S:IF (R<V AND R>L) OR V=L THEN V=R
50 IF W>1 THEN U=U*3:GOTO30
60 IF T<V THEN T=T*5:GOTO20
70 L=V:NEXT K:PRINT i,TIMER
On obtient les temps suivants :

Code : Tout sélectionner

Rang  Hamming  Tps FB  Tps V2
 10        12     0,8     4,2
 20        36     2,4    12,3
 30        80     5,1    23,4
 40       144     9,1    36,9
 50       243    15,2    52,9
 60       384    23,9    70,9
 70       576    35,8    90,4
 80       800    49,6   112,5
 90      1152    71,4   136,1
100      1536    95,1   161,6
110      2048   126,8   187,8
120      2700   167,2   216,1
130      3600   223,2   245,7
140      4500   279,3   278,0
150      5832   362,3   310,6
On constate une inversion du temps à partir de H(140) et la densité plus faible qui compense la complexité du calcul de la version 2.

En poussant un peu, j'ai fait la même chose sur HP39GII et ô joie les résultats sont alors bien meilleurs tout de même pour la version 2 à partir du 100e Hamming :

Code : Tout sélectionner

Rang  Hamming  Tps FB  Tps V2
 50       243     0,5       1
100      1536     2,5     2,5
150      5832       9       5
200     16200    25,5       8
250     38880    61,3    11,5
300     82944     131    15,5
350    164025     264      20
400    311040   503,5      25
Bon, reste plus qu'à oublier ces programmes de débutants... :(
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 »

J'y crois pas, en adaptant le code de C.ret et en collant un modulo sur les indices (histoire de faire tourner mon buffer de 500 nombres), je trouve H(1000)=51 200 000 en 66,1 s sur le Z1gr.
Et bien sur le temps est proportionnel à n et indépendant de la densité...

Code : Tout sélectionner

10 CLEAR:DIM H(500):N=1:A=2:B=3:C=5:INPUT R:TIMER=0
20 H(O MOD 500)=N:O=O+1:IF A=N THEN A1=(A1+1)MOD500:A=2*H(A1)
30 IF B=N THEN B1=(B1+1)MOD500:B=3*H(B1)
40 IF C=N THEN C1=(C1+1)MOD500:C=5*H(C1)
50 IF A<B AND A<C THEN N=A ELSE IF B<C THEN N=B ELSE N=C
60 IF O<R THEN 20
70 PRINT H((O-1)MOD500);TIMER
H(2000)=8 062 156 800 en 2'15"3...

Reste à voir la limite du buffer (ici 500).
Bravo pour l'optimisation, surtout que le programme reste court !
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 »

La nuit porte conseil, et de toute façon j'ai passé l'âge de faire nuit blanche, et j'ai repris le code comme suit en modifiant le calcul du modulo pour le calcul de A mais pas pour la position du pointeur.
Du coup en affichage, je peux utiliser la valeur du pointeur la plus faible (toujours C1) et donc afficher la taille du buffer utile pour atteindre le calcul en cours et en plus je gagne quelques dixièmes de secondes (ce qui m'étonne un peu d'ailleurs) :

Code : Tout sélectionner

10 CLEAR:DIM H(500):N=1:A=2:B=3:C=5:INPUT R:TIMER=0
20 H(O MOD 500)=N:O=O+1:IF A=N THEN A1=A1+1:A=2*H(A1 MOD500)
30 IF B=N THEN B1=B1+1:B=3*H(B1 MOD500)
40 IF C=N THEN C1=C1+1:C=5*H(C1 MOD500)
50 IF A<B AND A<C THEN N=A ELSE IF B<C THEN N=B ELSE N=C
60 IF O<R THEN 20
70 PRINT H((O-1)MOD500);TIMER;O-C1+1
Ce qui donne les résultats suivants :

Code : Tout sélectionner

Rang        Hamming  Buffer   Temps
  50            243      28     2"7
 100           1536      46     5"9
 200          16200      74    12"0
 300          82944     100    18"4
 400         311040     121    24"9
 500         937500     141    31"5
 600        2460375     161    38"1
 700        5989240     179    44"7
 800       12754584     197    51"4
 900       26244000     213    58"1
1000       51200000     230  1'04"8
1500      859963392     304  1'38"8
2000     8062156800     369  2'13"
2500  5,36870912e10     431  2'47"5
Ah ben forcément, on se confronte à la précision de la machine... Pour passer cette limite, faut représenter les entiers sur plusieurs valeurs (bon courage pour les opérations).
Avec une cote mal taillée, je trouve une taille de buffer nécessaire pour atteindre un rang déterminé d'environ

Code : Tout sélectionner

(Rang^0,7)*1,8
ce qui permet d'estimer une taille de buffer d'environ 1100 à 1200 pour atteindre le rang 10000. Ca commence à faire beaucoup pour nos bécanes...
Et H(10e6), oula, avec un buffer de l'ordre de 25000 à 30000, pas possible (et en plus faudrait 18 à 19 heures de calculs sur la Z1GR).

Par contre, avec les limites imposées par la taille du buffer, il peut être intéressant de voir jusqu'où on peut aller avec les différents ordipoches en fonction de la taille mémoire disponible et de la précision interne de calcul en entiers.
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,
Très intéressant ! Je travaille sur une méthode sans buffer ;-) mais pour l'instant c'est lent et imprécis...

Côté hardware, c'est utile de travailler sur grozordi pour peaufiner les algorithmes et tester à des rangs très élevés, mais il faudrait aussi faire entrer au chausse-pieds dans nos pockets.
Je dis chausse-pieds, mais on pourrait quand même avoir des tableaux de 4000 nombres (en comptant 32 Ko de RAM et 8 octets par nombre) sur nos "petites" machines, pour une limite de calcul vers h(60000) d'après ta formule...
A+
G.E.
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 »

Je ne sais pas si on pourra aller plus loin sans adapter les calculs à la précision des bécanes. H(60000) doit avoir un paquet de chiffres (je dirais à vu de nez, autour de 40)...

J'ai fait un tableau avec la TI74 en plus, car elle a 14 chiffres de précision et avec la Sharp PC1403 car elle a un Basic limité et une taille de tableau limitée à 255 :

Code : Tout sélectionner

Rang        Hamming  Buffer    Z1GR     TI74   PC1403
  50            243      28     2"7      8"0     27"0
 100           1536      46     5"9     16"5     57"5
 200          16200      74    12"0     34"5   1'59"5
 300          82944     100    18"4     52"5   3'03"5
 400         311040     121    24"9   1'11"0   4'08"5
 500         937500     141    31"5   1'29"5   5'14"0
1000       51200000     230  1'04"8   3'03"5  10'46"0
1500      859963392     304  1'38"8
2000     8062156800     369  2'13"
2500    53687091200     431  2'47"5   7'53"5
3000   278942752080     489  3'22"2   9'31"5
3500  1228800000000     543  3'57"3  11'10"0
4000  4701849845760     595    faux  12"49"0
4500 16124313600000     645          14'28"0
5000 50837316566580     693          16'07"5
J'ai poussé la Z1GR un peu plus loin (en augmentant le buffer à 1000) pour voir jusqu'où pouvait aller un résultat cohérent malgré sa précision à 10 chiffres : son calcul est bon (sur 10 chiffres significatifs) jusqu'à 3500 et qu'à 4000, du fait des erreurs d'arrondi, le buffer nécessaire devient plus gros (597 vs 595) et la valeur calculée sensiblement plus faible (4,6e12).

Pour le Sharp, pas de Modulo (comme sur la 74) et pas de ELSE non plus :

Code : Tout sélectionner

10 CLEAR:DIM H(255):N=1:A=2:B=3:C=5:INPUT R
20 H(O-INT(O/255)*255)=N:O=O+1:IF A=N LET A1=A1+1:A=2*H(A1-INT(A1/255)*255)
30 IF B=N LET B1=B1+1:B=3*H(B1-INT(B1/255)*255)
40 IF C=N LET C1=C1+1:C=5*H(C1-INT(C1/255)*255)
50 IF A<B AND A<C LET N=A:GOTO 60
52 IF B<C LET N=B:GOTO 60
55 N=C
60 IF O<R THEN 20
70 PRINT "H";H(O-1-INT((O-1)/255)*255);"B";O-C1+1
La limite de calcul avec cet algo doit donc être aux alentours de 1100/1150. Ce qui est déjà suffisant pour friser l'arrêt cardiaque à force d'attendre le résultat... :slime:

Le code de la 74 est le même que pour la Z1GR sauf pour le modulo inexistant.
A noter que la 74 va plus vite avec une taille de buffer plus grande (les calculs ont été faits avec une taille de 1500, mais avec une taille de 700, H(4000) prend 20" de plus 8O ). La Z1GR ne varie pas d'un iota en fonction de la taille allouée.
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 »

Un petit lien : Mal de crâne assuré...

Et en effet, il y a bien d'autres méthodes... Bouh :(
Avec une méthode volumétrique pas piquée des hannetons mais qui laisse H(10^18) accessible sur un micro récent.
Et H(10^6) peut-être sur nos vieux tromblons.

Dis-donc C.Ret, c'est un peu la charade à tiroirs ton MRA !!! :mrgreen: :mrgreen: :mrgreen:

Comme le dit la pub : et c'est pas fini.
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 »

Quelqu'un a-t-il réussi à garder des cheveux sur les méthodes avancées qui sont proposées ? Pourtant, ça donne envie... Surtout vu les perfs annoncées par rapport aux algos déjà expérimentés.

Perso j'abdique, sans plus d'accessibilité mathématique à la description des algos décrits par les chercheurs de l'inria (du calcul récursif sur des volumes de tétraèdres avec des coordonnées logarithmiques et autres joyeusetés. Je comprends mieux les liens avec les gammes diatoniques :roll: ).
Et les codes proposés sont en langage maison (Ocaml), j'arrive pas à m'en inspirer pour comprendre la démarche. :( Et j'ai pas envie d'essayer d'apprendre encore un autre langage, sauf de l'assembleur Saturn et Z80 :mrgreen: )

Du coup, C.ret, t'as réussi à implémenter quelque chose ?
En tout cas, la barre pour moi est bien trop haute comme ça (un peu comme un gamin qui voudrait battre le record de Lavillenie avec un cure-dent).
C'est du velu, velu... Ma licence de maths est bien trop loin...
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,
Je tapote un programme qui fera l'algorithme du paragraphe 3.2.
Mais le meilleur est le 3.3...
D'ailleurs si on lit attentivement le paragraphe 2.2., on peut optimiser l'algorithme publié au-dessus, mais c'est moins excitant que les deux autres.

J'ai tenté une méthode directe qui aurait été instantanée si des imprécisions impossibles à supprimer n'en empêchaient le fonctionnement.
Allez pour vous faire plaisir :twisted: un petit aperçu.
Si vous êtes allergique, SVP arrêtez de lire ici.

<folie mathématique=on>
Supposons que l'on dispose d'une fonction NH(m) qui donne le nombre de nombres de Hamming inférieurs ou égaux à m.
Il est clair que le nième nombre de Hamming H(n) vérifie : NH(H(n)) = n et NH(H(n)-1) = n-1.
Si on résoud en x l'équation : NH(x) = n - 0.5, on trouvera à peu près (H(n) - 0.5).
Donc le nième nombre de Hamming est donné par : H(n) = int(1 + Solve(NH(x) = n - 0.5) )
Et c'est quasiment instantané si le calcul de NH est rapide !!!
Cherchons donc la fonction NH.
On en connaît une expression compliquée par comptage :
NH(n) = Somme(a=0 à int( log(n)/log(5) ) de
Somme(b=0 à int( (log(n)-a*log(5))/log(3) ) de
Somme(c=0 à int( (log(n)-a*log(5)-b*log(3))/log(2) ) de 1 ) )

[ ça revient à compter 1 à chaque fois qu'on trouve a, b et c tels que 5^a*3^b*2^c < n, autrement dit
a*log(5)+b*log(3)+c*log(2) < log(n) ]

On ne peut pas trouver d'expression simple de ceci...
Mais si on retire les int(), l'expression se simplifie et vous pouvez la taper sur une machine à calcul formelle, j'ai tapé sur la Prime et ça donne un truc...
Au final on trouve à peu près en passant en valeurs numériques :
NHapprochée(n) = 0.135337*log(n)^3 + 0.681371*log(n)^2 + 1.1188632*log(n)+0.6
Malheureusement en écrivant le truc Solve() on trouve des valeurs proches du but mais inexactes, et d'ailleurs la courbe de la différence NH(n)-NHapprochée(n), on trouve des écarts de +/- 1.5 maximum sur les 20000 premières valeurs de n, très bien mais pas suffisant.
Comme ce graphe est très compliqué, pas moyen de trouver le terme d'erreur et donc PLOUF ce truc tombe à l'eau.
D'ailleurs si c'était possible d'autres gars auraient sûrement trouvé le truc depuis longtemps
</folie mathématique=off>
A part ça j'ai une vie passionnante !! :lol:

Sinon, l'intérêt du MRA est de faire tourner un truc incroyable sur nos petites machines, je pense que le grozordi ou même des langages bizarres c'est non ! Basic Power !!
J'espère vous proposer "bientôt" un truc sur Sharp.
A+
G.E.

EDIT : ça marche !! H(1234)=210937500, H(2222)=19371024450 etc etc :D
Listing Sharp demain avec explications, et je passe au 3.3.
Modifié en dernier par gege le 09 oct. 2015 02:14, modifié 2 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 »

Merci pour ta lecture gege !

Je vais essayer de me replonger dans le doc avec ton analyse, en quelques lignes tu rends tout de suite les concepts plus simples... :)
Une chose est sûre, on ne recrutera pas les gars de l'INRIA pour faire des articles dans la gazette ! :mrgreen: :mrgreen: :mrgreen:

Et sinon, je suis totalement d'accord avec toi : le MRA se limite aux vieilles bécanes et pour rester uniforme, d'utiliser le BASIC en langage principal (ce qui permet justement un comparatif des algorithmes implémentés).
(même si je pense tenter parfois le saut de l'assembleur, du C et du Forth qui peuvent être disponibles sur nos ordipochosaures).

Bon courage pour la suite des investigations ! :geek:
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

bernouilli92 a écrit :
gege a écrit :@C-Ret : très très bien ton algo.
Rendons à César ce qui est à Cézar, ce n'est pas tout à fait mon algo, je me suis bien inspiré des travaux donnés justement en référence par caloubugs
caloubugs a écrit :Un petit lien : Mal de crâne assuré...

Et c'est justement parce que je ne comprenais pas tous les tiroirs et détails, que l'idée m'est venue d'en faire un MPO/MRA.

Et je me réjouis en vous lisant, je me rends compte que je ne suis pas le seul à vivre une vie passionnante et à chercher à comprendre quelque chose.
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.
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,
Voici un programme de calcul du nombre de Hamming d'indice N donné par l'utilisateur.

Il s'agit de l'algorithme présenté au paragraphe 3.2 du document de l'INRIA mentionné ci-dessus.

Pour l'écrire j'ai d'abord dessiné un organigramme, puis testé sous Free Basic sur le PééCéé : un grand écran et un clavier sont vraiment utiles pour dénicher les bugs.
Ceci a validé l'algorithme, qui a été alors converti quasiment tel quel en Basic Sharp, et chargé sur un PC-E500 dans Pockemul.
Il faudra tout retaper sur la machine réelle afin de faire quelques mesures de rapidité, pour l'instant les résultats sont les suivants en vitesse normale sur Pockemul :

Code : Tout sélectionner

Rang        Hamming  Buffer   Temps	Comptage double précision
  50            243      28     2"7	 3"
 100           1536      46     5"9	 5"
 200          16200      74    12"0	 9"
 300          82944     100    18"4	15"
 400         311040     121    24"9	22"
 500         937500     141    31"5
 600        2460375     161    38"1
 700        5989240     179    44"7
 800       12754584     197    51"4
 900       26244000     213    58"1
1000       51200000     230  1'04"8
1500      859963392     304  1'38"8	1'26"
2000     8062156800      369  2'13"	1'59"
2500  5,36870912e10     431  2'47"5	2'37" 53687091200
5000                                  6'08" 50837316566580
6374                                  9'12" 839808000000000
Au-delà de 1000, la simple précision ne suffit plus, on trouve H(1500) = 859963395 et H(2000) = 8062156821. On utilise donc la double précision.

On n'utilise aucune particularité du Basic, et le portage vers une autre machine devrait être simple.
J'ai tenté de porter le programme sur Prime mais elle est dépourvue de GOTO, ce qui empêche les développements un peu complexes.


L'algorithme repose sur trois étapes :

- D'abord on compte les nombres de Hamming dans des tranches bornées par les puissances de 2.
Appellons n(2^k) le nombre de nombres de Hamming inférieurs ou égaux à 2^k (on reprend les notations du document de l'INRIA).
Il y a une formule permettant de calculer n(2^k) en fonction de n(2^(k-1)) avec une boucle.
On est donc capable de trouver k et n(2^k) tels que : n(2^(k-1)) < N ≤ n(2^k).
C'est ce que font les lignes 210 à 240 du programme.

- Ensuite on calcule tous les nombres de Hamming entre 2^(k-1) et 2^k (je vais revenir sur le comment), et on les insère un par un dans une liste doublement chaînée pour les trier.
L'insertion est faite lignes 400 à 510.

- Maintenant on a une liste triée dont le plus grand nombre est le n(2^k)-ième nombre de Hamming, il suffit de redescendre dans la liste de (n(2^k)-N) nombres pour y lire le N ième nombre de Hamming !

Voici le programme :

Code : Tout sélectionner

100 REM --------------------------
110 REM Suite de Hamming par comptage
120 REM --------------------------
130 DIM NH(20),LH#(1000),P(1000),S(1000)
140 REM --------------------------
150 REM NH = 2,4,7,12,19,27,38,45,68...
160 REM N indice de Hamming cherche
170 REM K indice de la tranche
180 REM --------------------------
190 L3#=log(3#)/log(2#):L5#=log(5#)/log(2#)
200 INPUT "Indice ";N:K=1:NH(1)=2
210 IF N<NH(K) THEN 330
220 K=K+1:T=INT(K/L5#):U=T+1
230 FOR I=0 TO T:U=U+INT((K-I*L5#)/L3#):NEXT I
240 NH(K)=NH(K-1)+U:GOTO 210
250 REM--------------------------
260 REM liste chainee :
270 REM  LH() logarithme
280 REM  P() precedent - 0=debut
290 REM  S() suivant   - 0=fin
300 REM  T   pointeur actuel
310 REM  U   nombre d'elements
320 REM--------------------------
330 T=1:U=1
340 LH#(1)=K:P(1)=0:S(1)=0
350 REM --------------------------
360 A=K:goto 540
370 B=INT((K-A)/L3#)
380 F#=A+B*L3#:C=INT((K-F#)/L5#):F#=F#+C*L5#
390 IF F#<=K-1 THEN 530
400 REM <<< Insertion >>>
410 U=U+1:LH#(U)=F#:IF F#>LH#(T) THEN 470
420 REM descend
430 R=P(T):IF R=0 THEN P(T)=U:P(U)=0:S(U)=T:GOTO 500
440 T=R:IF F#<LH#(T) THEN 430
450 S(U)=S(T):P(U)=T:P(S(T))=U:S(T)=U:GOTO 500
460 REM monte
470 R=S(T):IF R=0 THEN S(T)=U:P(U)=T:S(U)=0:GOTO 500
480 T=R:IF F#>LH#(T) THEN 470
490 P(U)=P(T):S(U)=T:S(P(T))=U:P(T)=U
500 T=U
510 REM << Fin insertion >>
520 C=C-1:IF C>-1 THEN F#=F#-L5#:GOTO 390
530 B=B-1:IF B>-1 THEN 380
540 A=A-1:IF A>-1 THEN 370
550 REM --------------------------
560 R=1:FOR I=1 TO NH(K)-N:R=P(R):NEXT I
570 PRINT "Hamming(";N;")=";INT(2^LH#(R)+0.5)
(1725 octets + 26680 octets pour les données)

Pour la liste triée on utilise outre les valeurs qu'on stocke dans le tableau LH, deux tableaux P et S pour "précédent" et "suivant".
Lorsqu'on veut insérer ligne 410 le nombre F, on a le pointeur U vers la dernière cellule utilisée qu'on incrémente et on stocke F dans LH. Il faut maintenant ajuster P(U) et S(U) et d'autres choses.
On a aussi un pointeur T vers le dernier point où on a inséré, on regarde ligne 410 si F est supérieur ou inférieur à LH(T), auquel cas on va monter ou descendre dans la liste.
Supposons qu'on monte, on arrive lignes 470 à 490. On utilise T comme pointeur actuel et R comme "suivant", on fera R=S(T) pour se déplacer. Il peut arriver deux choses :
- on arrive au bout de la liste, R vaut zéro qui signifie "fin de liste", on insère au bout ligne 470, ou
- on voit que F dépasse LH(T) et il faut insérer avant la position T, ligne 490.

Pour la troisième étape de l'algorithme (voir ci-dessus), en ligne 560 on part de l'élément d'indice 1 de la liste chaînée, en effet on sait que c'est le plus grand nombre de Hamming, car on l'a inséré en premier en ligne 340.
On boucle NH(K)-N fois et bingo ! Voilà notre nombre de Hamming, comme on avait en fait stocké le logarithme base 2 de sa valeur, on élève 2 à la valeur et c'est ter-mi-né !!

Ah oui, la génération de tous les nombres de Hamming entre 2^(k-1) et 2^k, j'ai failli oublier de vous en parler ;-) ... Ce sont les lignes 360-390 et 520-540.
Tout d'abord on utilise les fameuses "coordonnées logarithmiques multi-dimensionnelles", en fait ce truc ronflant veut tout simplement dire qu'on stocke le logarithme au lieu des nombres.
En effet si N = 2^a * 3^b * 5^c, alors log(N) = a*log(2) + b*log(3) + c*log(5)
Ce qui est bien plus facile à calculer en ne faisant que des multiplications !
Encore mieux, avec le logarithme en base 2 on a que le log2 de 2 vaut 1, une des trois constantes disparaît, encore plus simple ! (il y a aussi une autre raison pour choisir la base 2, je passe...)
Voilà pourquoi on définit L3 et L5 ligne 190.
Comparer N1 et N2 est pareil que comparer log2(N1) et log2(N2).

Pour générer les nombres... en gros on boucle en descendant sur A qui démarre à k-1 (ligne 360), puis B (ligne 370) puis C (ligne 380) et on sort des boucles quand la valeur calculée du log F n'est plus supérieure à (k-1) car alors le nombre est inférieur à 2^(k-1), donc plus dans notre tranche.

Bonne chasse pour la suite !
G.E.
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,
Pas besoin de retaper le programme sur le Sharp, grâce à la super interface USB de Manfred Becker !
Quelques secondes suffisent et les tests montrent que la machine réelle (la mienne en tout cas) est moins rapide que Pockemul en vitesse normale.
En rajoutant la ligne suivante on voit la taille utilisée dans les tableaux :

Code : Tout sélectionner

580 PRINT "Buffers :";K;U
Voici quelques résultats :

Code : Tout sélectionner

Rang  Buffers Pockemul Sharp
 100  11/ 23     5"       7"
 400  19/ 60             27"
 700  23/ 85    22"      47"
1500  30/138  1'26"    1'42"
2000  33/166  1'59"    2'20"
Je m'aperçois donc que l'espace réservé en ligne 130 est beaucoup trop grand (sauf pour NH), il suffit de mettre :

Code : Tout sélectionner

130 DIM NH(40),LH#(200),P(200),S(200)
Avec ces réglages on va tranquillement jusqu'à 2500, et la RAM consommée tombe à 5600 octets.
Finalement cet algorithme n'est pas si rapide que cela...
G.E.
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 »

Je ne pouvais pas rester insensible à ce travail !

Un seul mot, bravo !

Du coup, j'ai testé ton code et il y a des réels gains de performance mais ce n'est pas uniforme.

D'abord, j'ai repris le code de C.Ret sur le remplacement de la fonction min(a,b,c) pas implémentée sur la plupart des machines et dans mon code, j'imbriquais inutilement 2 IF. Je gagne alors à peu près 5 % de temps (lignes 50 et 55)

Code : Tout sélectionner

10 CLEAR:DIM H(500):N=1:A=2:B=3:C=5:INPUT R:TIMER=0
20 H(O MOD 500)=N:O=O+1:IF A=N THEN A1=A1+1:A=2*H(A1 MOD500)
30 IF B=N THEN B1=B1+1:B=3*H(B1 MOD500)
40 IF C=N THEN C1=C1+1:C=5*H(C1 MOD500)
50 N=A:IF N>B THEN N=B
55 IF N>C THEN N=C
60 IF O<R THEN 20
70 PRINT H((O-1)MOD500);TIMER;O-C1+1
J'ai aussi intégré le code suivant pour la HP35S qui permet facilement de gérer un tableau de 800 valeurs par adressage indirect :

Code : Tout sélectionner

H001 LBL H  CLVARS  1  STO N  2  STO A  3  STO B  5  STO C
H011 INPUT R  RCL O  500  RMDR  STO I  RCL N  STO(I)  1  STO+ O  RCL A
H021 RCL N  x!=y?  GTO H034  1  STO+ E  RCL E  500  RMDR  STO I  RCL(I)
H031 2  *  STO A  RCL B  RCL N  x!=y?  GTO H048  1  STO+ F  RCL F 
H041 500  RMDR  STO I  RCL(I)  3  *  STO B  RCL C  RCL N  x!=y? 
H051 GTO H062  1  STO+ G  RCL G  500  RMDR  STO I  RCL(I)  5  * 
H061 STO C  RCL A  STO N  RCL B  x<y?  STO N  RCL N  RCL C  x<y?  STO N
H071 RCL O  RCL R  x>y?  GTO H012  1  STO- O  RCL O  500  RMDR  STO I
H081 RCL(I)  RCL O  RCL- G  2  +  RTN
Il faut juste taper 500 STO I 1 STO(I) pour initialiser le tableau de 500 valeurs avant de lancer le programme.
J'obtiens le tableau de temps suivant :

Code : Tout sélectionner

Rang        Hamming  Buffer    Z1GR     TI74   PC1403    HP35S
  50            243      28     2"6      7"5     26"0     23"5
 100           1536      46     5"5     15"5     55"0     50"0
 200          16200      74    11"6     33"0   1'54"5   1'45"5
 500         937500     141    30"2   1'25"5   5'00"5   4'39"0
1000       51200000     230  1'01"8   2'55"5  10'19"5   9'36"0
2000     8062156800     369  2'07"2   5'59"5
3000   278942752080     489  3'13"4   9'07"5
4000  4701849845760     595    faux  12"17"0
5000 50837316566580     693          15'27"0
Et maintenant en adaptant ton code à quelques machines :

Code : Tout sélectionner

 Rang        Hamming  Buffer    Z1GR      gain   PC1403      gain  
   50            243   8/ 14     2"7  +  4,0 %     20"5  - 21,2 %
  100           1536  11/ 23     5"1  -  7,2 %     39"0  - 29,1 %
  200          16200  14/ 34     7"9  - 31,9 %   1'02"5  - 45,4 %
  500         937500  20/ 65    21"3  - 29,5 %   2'52"0  - 38,4 %
 1000       51200000  26/107    48"6  - 21,4 %   6'39"0  - 35,6 %
 2000     8062156800  33/166  1'40"7  - 20,8 %  13'58"0  incorrect sur 
 3000   278942752080  39/228  2'56"3  -  8,8 %           les 2 derniers
 4000  4701849845760  43/275  4'04"6  exact !!!          chiffres (21)
 5000 50837316566580  46/313  5'09"9  exact !!!
10000 2.883251953e17  59/504 12'24"1  à vérifier
Le plus surprenant est l'impact différent suivant les machines... Plus marqué sur la 1403 que sur la Z1GR. Faut dire aussi que les calculs de modulo faussent la donne, la 1403 devant faire plus de calculs dans la version initiale.
Et la courbe en cloche du gain (avec un maximum de gain vers 200 puis une diminution progressive de l'avantage de cet algorithme). En effet, l'utilisation de 3 buffers augmente plus rapidement le nombre de calculs à réaliser et compense insuffisamment le gain en terme de calculs de nombres de Hamming.

Par contre, il permet aussi d'aller a priori plus loin, car avec 10 chiffres significatifs, la Z1GR était fausse à 4000 (sur sa mantisse) alors que les 10 chiffres sont bons désormais à 5000. J'ai poussé jusqu'à 10000 mais il faudrait pouvoir comparer avec le résultat exact (pas encore calculé). C'est quand même un avantage important de cet algo.
Pour la Sharp, on remarque aussi qu'avec 3 buffers de 200 (limite mémoire de la 1403 atteinte), on peut dépasser l'ancienne limite de calcul. Une petite erreur cependant pour le calcul du 2000ème.
Je vais voir pour en faire une adaptation en langage structuré, c'est vrai qu'avec tous ces GOTO, c'est quelque peu pénible pour adapter...
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,
Youpie, chouettes résultats !
C'est une bonne idée la HP35S, reste à lire ton code...

Avec 10 chiffres en flottant on a des soucis au-delà de 1000, car le nombre de Hamming est supérieur à 10^9 et on n'a plus assez de décimales.
Sur Pockemul pour 10000 je trouve 288325195312500000, on doit pouvoir aller un tout petit peu plus loin car cela ne fait "que" 18 chiffres, le Sharp en a 20 sous le coude !!!

On est limités par la précision (la RAM c'est tranquille), mais il reste peut-être quelque chose à faire sur la vitesse avec l'algorithme du paragraphe 3.3.
On pourrait aussi tricher en précalculant les tranches vu qu'on a "trop" de RAM, ça donnerait ça :

Code : Tout sélectionner

200 INPUT "Indice ";N:K=0
210 K=K+1:READ M:IF N<M THEN 330 ELSE 210
220 DATA 2,4,7,12,19,27,38,52,68,87,110,137,167,201
225 DATA 240,284,332,386,446,511,582,660,745,836,934
230 DATA 1041,1155,1277,1407,1545,1692,1849,2015,2190
235 DATA 2376,2571,2777,2994,3222,3461,3711,3974,4249
240 DATA 4535,4834,5147,5473,5811,6164,6531,6911
245 DATA 7306,7716,8142,8582,9039,9511,9999,10503
560 R=1:FOR I=1 TO M-N:R=P(R):NEXT I
A bientôt,
G.E.
Répondre

Retourner vers « Tous les Pockets »