petit defi, réelle optimisation

petit defi, réelle optimisation - ASM - Programmation

Marsh Posté le 26-02-2005 à 01:28:22    

Vous connaissez très certainement la procedure de generation de nombres aléatoire proposée par masm32... sinon, la  voici :

Code :
  1. ; #########################################################################
  2. ;
  3. ;                     Park Miller random number algorithm.
  4. ;
  5. ;                      Written by Jaymeson Trudgen (NaN)
  6. ;                   Optimized by Rickey Bowers Jr. (bitRAKE)
  7. ;
  8. ; #########################################################################
  9.       .486                      ; create 32 bit code
  10.       .model flat, stdcall      ; 32 bit memory model
  11.       option casemap :none      ; case sensitive
  12.     .code
  13. ; #########################################################################
  14. nrandom PROC base:DWORD
  15.     mov eax, nrandom_seed
  16.     xor edx, edx
  17.     mov ecx, 127773
  18.     div ecx
  19.     mov ecx, eax
  20.     mov eax, 16807
  21.     mul edx
  22.     mov edx, ecx
  23.     mov ecx, eax
  24.     mov eax, 2836
  25.     mul edx
  26.     sub ecx, eax
  27.     xor edx, edx
  28.     mov eax, ecx
  29.     mov nrandom_seed, ecx
  30.     div base
  31.     mov eax, edx
  32.     ret
  33. nrandom ENDP
  34. ; #########################################################################
  35. nseed proc TheSeed:DWORD
  36.     .data
  37.       nrandom_seed dd 12345678
  38.     .code
  39.     mov eax, TheSeed
  40.     mov nrandom_seed, eax
  41.     ret
  42. nseed endp
  43. ; #########################################################################
  44.     end


 
Bien, alors vous remarquerez que cette procedure à été (en plus) "optimisée" par un tiers... Je ne sais pas en quoi consistait l'optimisation, mais moi je vais vous montrer comment on optimise réellement ce genre de procedure... mais avant ça, peut être que quelqu'un à une proposition a faire ?


Message édité par NightWare le 26-02-2005 à 23:47:15
Reply

Marsh Posté le 26-02-2005 à 01:28:22   

Reply

Marsh Posté le 26-02-2005 à 23:25:12    

:(  40 lectures et personne ne veut s'y essayer ?
Ok, alors j'y vais, pour optimiser la routine, il faut evidement supprimer les instructions qui coutent énormément en cycle d'horloge, on va donc supprimer les divisions. Pour ca, on va utiliser un principe mathematique simple : X divisé par 2 est égal à X multiplier par 0,5 (et inversement). donc, chaque division posséde une équivalence en multiplication. bien sûr ca se complique un peu en base 2 (binaire), mais pas tant que ca...
Il suffit, pour obtenir la valeur recherchée, de faire l'opération suivante 4 294 967 295 (pour un registre 32 bits) divisé par la valeur (ici, 127 773) et on obtient : 3 3614.044...
a ces 3 3614 (l'entier) on va ajouter 1 (c'est necessaire parceque le registre est en fait égal à 4 294 967 295 plus le zéro, soit 4 294 967 296 valeurs possible). Pourquoi on ajoute ce 1 au résultat et pas à la valeur de départ ? et bien je ne vais pas rentrer dans le détail, mais vous devez savoir que c'est là qu'il faut le placer.
 
petit example : au hasard, la valleur 2 000 000
 
2 000 000 / 127 773 = 15,65... (placé respectivement dans eax et edx)
2 000 000 * 3 3615 = 67 230 000 000 (mais ce nombre excéde le registre eax, la valeur correspondante est donc envoyée dans edx)
et comme par hasard (ça c'est vraiment de la magie magique !) 67 230 000 000 / 4 294 967 295 = 15,65... on a donc 15 placé en edx
 
bravo ! vous avez compris, au lieu d'extraire par le bas (vers la droite) on extrait par le haut (la gauche)
et pour la deuxieme division une multiplication par la valeur maximale est amplement suffisante car le processus obtenu (tout comme l'original) génére toujours des nombres très volumineux avant d'effectuer la manipulation par la base (valeur maximale)
 
Ensuite, on constatera (à l'usage) que la routine genére uniquement des nombre aléatoires pair ou impair, et ce, en fonction de la valeur de départ dans nrandom_seed (ben oui, faire des manipulation d'entier avec 2 nombres impair et finir avec 1 nombre pair, ce n'est pas très judicieux) on va donc modifier la valeur de la multiplication paire de la routine et la transformer en valeur impaire (ce qui générera des nombres pair ET impair, quelque soit la valeur de départ)
 
Enfin, on va transformer la procédure en macro, ca evite des sauts/retours inutiles, car ce genre de procedure n'est jamais appelée suffisament dans un programme pour justifier du statut de procédure. dailleurs, la petite taille de la routine obtenue justifie, à elle seule, le statut de macro (en asm, il n'y a pas de petites économies)
 
ce qui donne la macro :
 

Code :
  1. ; #########################################################################
  2. ; origine : Park Miller random number algorithm.
  3. ; + Jaymeson Trudgen (NaN)
  4. ; + Optimized by Rickey Bowers Jr. (bitRAKE)
  5. ; + NightWare
  6. ;
  7. ; generer un nombre aleatoire non-signé 32-bits entre 0 et une valeur maximale (excluse)
  8. ; Réceptionne : la valeur maximale (elle doit être supérieur à 1)
  9. ; Retourne: le nombre aleatoire en eax
  10. ; syntaxe : nrandom [Valeur Maximale]
  11. ; #########################################################################
  12. nrandom MACRO base:REQ
  13. ECHO GenererNombreAleatoireDefini
  14. push ebx    ;; empiler ebx
  15. push ecx    ;; empiler ecx
  16. push edx    ;; empiler edx
  17. mov eax,nrandom_seed   ;; placer l'aléatoire précedent dans eax
  18. mov ebx,33615    ;; placer 33615 dans ebx
  19. mul ebx     ;; multiplier eax par 33615
  20. mov ecx,edx    ;; sauvegarder edx dans ecx
  21. mov ebx,16807    ;; placer 16807 dans ebx
  22. mul ebx     ;; multiplier eax par 16807
  23. mov ebx,ecx    ;; placer la sauvegarde en ecx dans ebx
  24. mov ecx,eax    ;; sauvegarder eax dans ecx
  25. mov eax,2973    ;; placer 2973 dans eax
  26. mul ebx     ;; multiplier eax par la sauvegarde ebx
  27. sub ecx,eax    ;; soustraire eax à ecx
  28. mov nrandom_seed,ecx   ;; sauvegarder le nouveau nombre aléatoire pour la génération du prochain
  29. mov eax,ecx    ;; placé le nouveau nombre aléatoire en ecx dans eax
  30. mov ebx,base    ;; placer la valeur maximale en ebx
  31. ; inc ebx     ;; (optionnel) incrementer ebx de 1 (si l'on veut que la valeur maximale soit incluse)
  32. mul ebx     ;; multiplier le nombre aléatoire par la valeur maximale
  33. mov eax,edx    ;; et placer le dépassement en eax
  34. pop edx     ;; désempiler edx
  35. pop ecx     ;; désempiler ecx
  36. pop ebx     ;; désempiler ebx
  37. ENDM


 
conclusion : cette macro complète, malgrès les pushs et les pops, est plus rapide qu'une seule des divisions de la routine de départ... c'est de l'optimisation ça, non ?
 
personnellement, j'utilise une variante de cette macro et je n'ai relevé aucun problème, maintenant si quelqu'un en trouve un, je lui serai reconnaissant de le signaler. idem si quelqu'un parviens à l'optimiser davantage, merci  ;)
 
edit : heu désolé, voila le code est dans des balises...


Message édité par NightWare le 27-02-2005 à 00:09:13
Reply

Marsh Posté le 26-02-2005 à 23:29:47    

poste ton code dans des balises [code ] [ /code]
 

Code :
  1. comme ceci


---------------
Jubi Photos : Flickr - 500px
Reply

Marsh Posté le 27-02-2005 à 00:13:57    

sinon y'a ça aussi, en plus sexy et 100% FPU [:petrus75]

Code :
  1. .386
  2. KK      equ     17
  3. JJ      equ     10
  4. RR      equ      7
  5. RAND_DATA SEGMENT PARA USE32 PUBLIC 'DATA'
  6. align   16
  7. randp1  DT      1.5
  8.         DW      0
  9. p1      DD      0
  10. p2      DD      0
  11. rbufend DD      (KK-1)*8
  12. randbuf DD      (2*KK) dup(?)
  13.         DD      ?
  14. one     DD      1.0
  15. RandAdd DQ      0.147328926107;
  16. RandFactor DQ   46.1063140045
  17. RandDiv DQ      0.0817835148503
  18. RAND_DATA ENDS
  19. DGROUP GROUP RAND_DATA
  20. _TEXT   SEGMENT DWORD USE32 PUBLIC 'CODE'
  21. ASSUME CS:_TEXT,DS:DGROUP
  22. PUBLIC Random1,_Random1,Random2,_Random2,RandomInit,_RandomInit
  23. Random1 PROC NEAR
  24. _Random1 LABEL NEAR
  25.         FLD     [randp1]
  26.         FSUB    [one]
  27. Random2 LABEL NEAR
  28. _Random2 LABEL NEAR
  29.         MOV     ECX, [p1]
  30.         MOV     EDX, [p2]
  31.         PUSH    EBX
  32.         NOP
  33.         MOV     EBX, [randbuf][ECX]
  34.         MOV     EAX, [randbuf][ECX+4]
  35.         ROR     EBX, RR
  36.         ADD     EBX, [randbuf][EDX]
  37.         ADD     EAX, [randbuf][EDX+4]
  38.         MOV     [randbuf][ECX], EAX
  39.         MOV     [randbuf][ECX+4], EBX
  40.         OR      EBX, 80000000H
  41.         MOV     DWORD PTR [randp1],EAX
  42.         SUB     ECX, 8
  43.         JNC     SHORT R1
  44.         MOV     ECX, [rbufend]
  45. R1:     MOV     DWORD PTR [randp1+4],EBX
  46.         POP     EBX
  47.         SUB     EDX, 8
  48.         JNC     SHORT R2
  49.         MOV     EDX, [rbufend]
  50. R2:     MOV     [p1], ECX
  51.         MOV     [p2], EDX
  52.         RET
  53. random1 ENDP
  54. RandomInit PROC NEAR
  55. _RandomInit LABEL NEAR
  56.         FLD1
  57.         FLD     QWORD PTR [ESP+4]
  58.         FTST
  59.         FSTSW   AX
  60.         SAHF
  61.         JNC     SHORT R20
  62.         FSUBR   [RandAdd]
  63.         JMP     SHORT R20
  64. R10:    FMUL    [RandDiv]
  65. R20:    FCOM    ST(1)
  66.         FSTSW   AX
  67.         SAHF
  68.         JAE     R10
  69.         MOV     ECX, OFFSET DS:[randbuf]
  70.         MOV     EDX, KK*2
  71. R30:    FSQRT
  72.         FADD    [RandAdd]
  73.         FMUL    [RandFactor]
  74.         FPREM
  75.         FST     QWORD PTR [ECX]
  76.         ADD     ECX, 4
  77.         DEC     EDX
  78.         JNZ     R30
  79.         FSTP    ST(0)
  80.         FSTP    [randp1]
  81.         MOV     [p1], (KK-JJ-1)*8
  82.         MOV     [p2], (KK-1)*8
  83.         CALL    Random2
  84.         RET     8
  85. RandomInit ENDP
  86. _TEXT   ENDS
  87.         END


j'aurais aimé avoir été l'auteur de ce code d'anthologie


Message édité par Harkonnen le 27-02-2005 à 00:19:19

---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 27-02-2005 à 00:38:48    

bonjour, je m'appelle harko, et je fais des PRN congruents à coup de virgule flottante ...

Reply

Marsh Posté le 02-03-2005 à 13:22:55    

Bonjour
Quelqu'un pourait-il me dire dans quelle occasion il est nécessaire d'avoir une procédure donnant un nombre aléatoire de façon ultra-rapide ?
Est-ce une optimisation pour la beauté de la chose ?
Y-a-t-il la version utilisant les registres xmm permettant de calculer plusieurs nombres à la fois ?

Reply

Marsh Posté le 02-03-2005 à 13:28:35    

NightWare a écrit :

:(  40 lectures et personne ne veut s'y essayer ?
Ok, alors j'y vais, pour optimiser la routine, il faut evidement supprimer les instructions qui coutent énormément en cycle d'horloge, on va donc supprimer les divisions. Pour ca, on va utiliser un principe mathematique simple : X divisé par 2 est égal à X multiplier par 0,5 (et inversement). donc, chaque division posséde une équivalence en multiplication. bien sûr ca se complique un peu en base 2 (binaire), mais pas tant que ca...


Mauvais exemple, x / 2 est équivalent à X >> 1, ce qui est plus rapide encore ;)

Reply

Marsh Posté le 02-03-2005 à 13:31:01    

db__ a écrit :

Bonjour
Quelqu'un pourait-il me dire dans quelle occasion il est nécessaire d'avoir une procédure donnant un nombre aléatoire de façon ultra-rapide ?


bin quand tu fais des calculs necessitant bcp d'aleatoire (texture procedurale, par ex)
 

Citation :

Est-ce une optimisation pour la beauté de la chose ?


nope

Citation :


Y-a-t-il la version utilisant les registres xmm permettant de calculer plusieurs nombres à la fois ?


 
j'avais vu ca un coup avec du mmx. je sais pu si ca generait un nombre ou plusieurs, cependant

Reply

Marsh Posté le 02-03-2005 à 14:04:11    

c'est toujours interressant ce genre de trucs.

Reply

Marsh Posté le 02-03-2005 à 22:36:11    

db__ a écrit :

Bonjour
Quelqu'un pourait-il me dire dans quelle occasion il est nécessaire d'avoir une procédure donnant un nombre aléatoire de façon ultra-rapide ?
Est-ce une optimisation pour la beauté de la chose ?
Y-a-t-il la version utilisant les registres xmm permettant de calculer plusieurs nombres à la fois ?


cette routine à énormémént d'utilité, et sa rapidité est vraiment importante... je vais prendre un example parlant : supposons que tu developpe un jeu video où ton personnage dois faire face à plusieurs adversaires (genre medal of honor, etc...). l'intelligence artificielle de chacun des adversaire dépend d'un choix (necessitant donc un nombre aléatoire) entre les diverses possibilités offertes à cette adversaire.
aussi si tu multipli les adversaires et que ta routine est bourrée de divisions, ben tu peut dire adieu à un Frame Per Seconds correct.
 
mais surtout, le but de mon post n'était pas de créer un nouveau PRNG, mais de montrer une methode d'optimisation, montrer qu'il est possible de supprimer toutes les divisions (instruction vraiment trop lente) de votre code. et ce, même si la division est utilisée avec une variable (dans ce cas là, on passe par une table). cette routine est quasiment celle qui est utiliséé par les pros du jeu video (et oui, on peut encore l'optimiser un peu, mais le gain n'est plus très important), si j'ai fait ce post c'est aussi parceque mettre 2 divisions dans un code et dire qu'on l'a optimisé, ben perso je trouve que ca prête a rire...
 
il est possible de transformer cette routine avec des instructions mmx sse, sse2, sse3... mais l'intêret est quasi inexistant, car cette routine à de réelles limites. en effet, plus la valeur maximale est importante et moins le nombre aléatoire est vraiment aléatoire (les petites valeurs disparaissent, c'est une limite de la routine originelle dailleurs...). mais plus important encore, il faudrait extraire les "dépassements" des registres xmm et ca, ca ralentirai pas mal la routine...
 
mais bon vu que vous avez l'air interessés par cette routine, ca fait 50 euros chacun ! (ben quoi ? faut bien vivre non ? halala... ok... au moins j'aurai essayé  :D )

Reply

Marsh Posté le 02-03-2005 à 22:36:11   

Reply

Marsh Posté le 02-03-2005 à 23:07:38    

c'est important d'optimiser, mais c'est pas non plus critque d'avoir un rand turbo-momoute qui va faire qu'un moteur 3D de jeu va être optimisé.

Reply

Marsh Posté le 13-03-2005 à 09:25:01    

NightWare a écrit :


personnellement, j'utilise une variante de cette macro et je n'ai relevé aucun problème, maintenant si quelqu'un en trouve un, je lui serai reconnaissant de le signaler. idem si quelqu'un parviens à l'optimiser davantage, merci  ;)
 
edit : heu désolé, voila le code est dans des balises...


Question bête : as-tu vérifié que les suites générées sont EXACTEMENT identiques à celles de la routine originelle (et ce même après quelques dizaines de millions d'appels) ?

Reply

Marsh Posté le 15-03-2005 à 02:20:20    

el muchacho a écrit :

Question bête : as-tu vérifié que les suites générées sont EXACTEMENT identiques à celles de la routine originelle (et ce même après quelques dizaines de millions d'appels) ?


 
 :heink:  ben si tu lis le code, tu remarqueras que j'ai remplacé texto la dernière division par une simple multiplication par le même chiffre (donc déjà là, je peut pas obtenir le "même" résultat qu'avec l'original).
 :wahoo:  ensuite, si tu veut savoir si la première multiplication remplace parfaitement la première division, ben la réponse est "mathèmatiquement" oui.
bref : si tu transforme la deuxième division également (c'est pas très pratique, mais c'est possible et facile à faire) et bien, tu obtiendras EXACTEMENT la même suite que la routine originelle...
 
 :D  maintenant, vu que c'est une routine qui génére des nombres aléatoires, je vois pas vraiment l'interêt d'obtenir EXACTEMENT la même suite que la routine d'origine... a moins que tu ait des besoins particuliers ???

Reply

Marsh Posté le 15-03-2005 à 09:17:26    

NightWare a écrit :


 :D  maintenant, vu que c'est une routine qui génére des nombres aléatoires, je vois pas vraiment l'interêt d'obtenir EXACTEMENT la même suite que la routine d'origine... a moins que tu ait des besoins particuliers ???


 
j'ai personnelement plus souvent besoin de pseudo aleatoire que d'aleatoire pur (et d'ailleurs ta routine c'est du pseudo aleatoire)

Reply

Marsh Posté le 15-03-2005 à 09:21:14    

chrisbk a écrit :

j'ai personnelement plus souvent besoin de pseudo aleatoire que d'aleatoire pur (et d'ailleurs ta routine c'est du pseudo aleatoire)


à part dans la crypto et le traitement du signal, on a rarement réellement besoin de vrai aléatoire.


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 17-03-2005 à 22:55:08    

chrisbk a écrit :

j'ai personnelement plus souvent besoin de pseudo aleatoire que d'aleatoire pur (et d'ailleurs ta routine c'est du pseudo aleatoire)


 
 :ouch:  c'est vrai, c'est du pseudo, je suis désolé d'avoir oublié "pseudo", et comme meaculpa je vous file une version encore plus rapide... (mais plus limitée...) j'ai marqué 256 comme limite, mais on peut aller tout de même beauoup plus haut (quelques dizaines de milliers).
 

Code :
  1. ;------------------------------------------------------------
  2. ; generer un nombre aleatoire 32-bits entre 0 et une valeur maximale (exclue), coût de 22 cycles d'horloge.
  3. ; Réceptionne : la valeur maximale (doit être de 256 au maximum, c'est une version turbo...)
  4. ; Retourne: EAX = nombre aleatoire entre 0 et la valeur maximale (exclue)
  5. ; syntaxe : GenererNombrePSEUDOAleatoireTurbo [Valeur Maximale]
  6. ;------------------------------------------------------------
  7. GenererNombrePSEUDOAleatoireTurbo MACRO ValeurMaxi:REQ
  8. LOCAL Label1,Label2
  9.  ECHO GenererNombrePSEUDOAleatoireTurbo
  10.  push ecx        ;; empiler ecx
  11.  push edx        ;; empiler edx
  12. ;  mov eax,1        ;; (optionnel) placer la valeur minimale en eax
  13. ;  cmp eax,ValeurMaxi      ;;  ) comparer eax à la valeur maximale
  14. ;  jl Label1        ;;  ) si la valeur maxi est supérieure aller Label1
  15. ;  xor eax,eax        ;;  ) sinon, effacer eax
  16. ;  jmp Label2        ;;  ) et sortir
  17. Label1: mov eax,NombreAleatoire     ;; placer l'aléatoire précedent dans eax
  18.  mov ecx,eax       ;; placer une sauvegarde de l'aléatoire dans ecx
  19.  shl eax,3        ;; ) multiplier eax par 7
  20.  sub eax,ecx        ;; )
  21.  add eax,7        ;; ajouter 7 au résultat
  22.  rcr ecx,3        ;; faire un décalage logique à droite de l'aléatoire sauvegardé en ecx de 3 bits
  23.  xor eax,ecx        ;; et pratiquer une inversion de bits avec l'aléatoire précedent modifié comme masque
  24.  mov NombreAleatoire,eax     ;; sauvegarder le nouveau nombre aléatoire pour la génération du prochain
  25.  mov ecx,ValeurMaxi      ;; placer la valeur maximale en ecx
  26. ;  inc ebx        ;; (optionnel) incrementer ebx de 1 (si l'on veut que la valeur maxi soit incluse)
  27.  mul ecx        ;; multiplier ensuite le nombre aléatoire par cette valeur maximale
  28.  mov eax,edx       ;; et placer le dépassement en eax
  29. Label2:
  30.  pop edx        ;; désempiler edx
  31.  pop ecx        ;; désempiler ecx
  32. ENDM

Reply

Marsh Posté le 22-03-2005 à 16:30:32    

heu, sans parler d'un test du khi²,
t'as essayé d'allumer quelques pixels avec ton code ?
tu risques d'avoir mal aux yeux en voyant ce minuscule motif (en diagonales) se répéter, se répéter...

Reply

Marsh Posté le 22-03-2005 à 18:18:05    

getNextRand :
entrée : ECX contient l'adresse de la graine initiale (de valeur quelconque)
sortie : la graine est mise à jour, EAX contient une nouvelle valeur pseudo-aléatoire sur 24 bits
 

Code :
  1. MOV EBX,7421
  2. MOV EAX,[ECX]
  3. MUL EBX
  4. INC EAX
  5. MOV [ECX],EAX
  6. SHR EAX,8


 
ou sur 32...
 

Code :
  1. MOV EBX,7421
  2. MOV EAX,[ECX]
  3. MUL EBX
  4. INC EAX
  5. MOV [ECX],EAX
  6. SHL EDX,16
  7. SHR EAX,16
  8. OR EAX,EDX


Message édité par fra0 le 22-03-2005 à 18:36:56
Reply

Marsh Posté le 22-03-2005 à 22:21:34    

oué et heuh, il a quel periodicité ce bout de code ? y mfait un peu peur, jdois dire [:petrus75]


---------------
NP: HTTP Error 764 Stupid coder found
Reply

Marsh Posté le 22-03-2005 à 22:57:08    

fra0 a écrit :

heu, sans parler d'un test du khi²,
t'as essayé d'allumer quelques pixels avec ton code ?
tu risques d'avoir mal aux yeux en voyant ce minuscule motif (en diagonales) se répéter, se répéter...


 
ben je l'ai testé avec un starfield, et le resultat m'a paru acceptable (ou du moins suffisant pour mes besoins...), pourquoi ? avec quoi tu l'as testé ?

Reply

Marsh Posté le 23-03-2005 à 01:41:20    

chris la périodicité est de 24 ou 32 bits (je vends ça avec une meilleure constante que 7421 450€) après j'ai pas remarqué de cycles, mais je n'en ai pas cherché.
 
Nightware, au temps pour moi j'avais mal intégré ta fonction (faut dire elle est tellement longue...)
 
sinon j'ai testé la portée avec min/max et une animation splittée, y'a pas de différence notable avec rand (et c'est 10x plus rapide) ni random (c'est 14x + rapide) mais c'est juste environ 2x plus rapide que ta version turbo
 
allé, fais de beaux rêves  :pt1cable:


Message édité par fra0 le 23-03-2005 à 04:04:03
Reply

Marsh Posté le 23-03-2005 à 15:43:43    

et hop, voici la mesure du khi² pour mon générateur (avec une grosse constante) pour 10000 nombres aléatoires entre [0 et 1000[
la valeur attendue pour un bon générateur est de 1000 +/- (1000^0.5) soit environ [969;1031]  
 
1013
965*
1020
1026
1007
979
1057*
927*
932*
974
976
1028
1006
1019
 
chaque ligne représente une graine différente,
certaines graines(*) empêchent la bonne distribution des valeurs
à titre comparatif, les résultats de random(1000) sous windows
 
1032*
986
953*
1026
976
975
952*
962*
982
981
1016
965*
1018
...

Reply

Marsh Posté le 23-03-2005 à 15:44:09    

edit : double post


Message édité par fra0 le 23-03-2005 à 15:50:18
Reply

Marsh Posté le 23-03-2005 à 22:02:32    


j'ai aussi testé mon générateur (#9357421) avec ENT (http://www.fourmilab.ch/random/)
 
voici la sortie pour un fichier de 32.000.000 de bits,
 
Entropy = 7.999957 bits per byte.
 
Optimum compression would reduce the size
of this 4000000 byte file by 0 percent.
 
Chi square distribution for 4000000 samples is 236.44, and randomly
would exceed this value 75.00 percent of the times.
 
Arithmetic mean value of data bytes is 127.4571 (127.5 = random).
Monte Carlo value for Pi is 3.143631144 (error 0.06 percent).
Serial correlation coefficient is 0.000508 (totally uncorrelated = 0.0).
 
-----
 
donc mon code est aussi un décompresseur parfait pour ce fichier....
d'après leur readme (et le khi²), il révèle même "a genuine random sequence created by timing radioactive decay events."

Reply

Marsh Posté le 24-03-2005 à 10:07:24    

et quelle est la suite de nombre qui maximise ce test ?

Reply

Marsh Posté le 24-03-2005 à 16:37:54    

sûrement quelque chose très proche du hasard (ou peut être une classe de fichiers qui parvient à le gruger :sweat: )
 
pour un truc codé en 5 minutes, je m'attendais à devoir faire beaucoup plus de réglages pour arriver à ce résultat.

Reply

Marsh Posté le 24-03-2005 à 23:27:02    

fra0 a écrit :

Nightware, autant pour moi j'avais mal intégré ta fonction (faut dire elle est tellement longue...)


 
tellement longue ? mais c'est très drôle ca...  ;)  
 

fra0 a écrit :

c'est juste environ 2x plus rapide que ta version turbo


 
2x plus rapide... hum... peut être... mais tu triches un peu... il faut rajouter une instruction pour mettre la valeur en ecx, et il faudrait aussi que tu empile/désempile ebx,ecx et edx pour la rendre aussi propre que la mienne (ou alors enlever ces manips avec la pile de la mienne)... tu crois pas ?  :D  
 

Reply

Marsh Posté le 25-03-2005 à 01:13:24    

c'est pas mon genre  :non:  
 
t'as compris le code au moins ?
 
j'ai testé les deux fonctions en C dans les mêmes conditions (mais bon je me suis pas attardé dessus non plus)
 
si tu veux d'autres chiffres :
 
j'ai un Athlon XP à 1466MHz
et dessus, ma fonction remplit 100x un tableau de 1 million de DWORDS  en 1.5 secondes : ça représente un fill rate de 254,3Mo/sec si mes caluls sont exacts*.
 
* edit : en plaçant la graine juste avant le tableau, ça monte à
264,5Mo/sec  
 
et, accroche toi...pour les buffers de moins de 256Ko plus de 357Mo/s
 
C'est même mieux que de piocher dans une table  :hello:


Message édité par fra0 le 25-03-2005 à 02:53:00
Reply

Marsh Posté le 25-03-2005 à 01:21:30    

on peut encore virer 2 instructions si t'es vraiment pressé petit padawan.
 

Code :
  1. B8xxxxxxxxF7218901C1E210C1E8100BC2


 
mais la graine devra être différente de 0 (...)
 
Cependant les tests d'entropie et de moyenne arithmétique d'ENT en seront légèrement boostés  :na:  
 

Reply

Marsh Posté le 25-03-2005 à 01:49:13    

fra0 a écrit :

sûrement quelque chose très proche du hasard


 
eheh
 

Reply

Marsh Posté le 25-03-2005 à 02:16:45    

n'ayons pas peur des mots : le hasard.
 
mais le hasard est tellement hasardeux qu'on sait jamais...
 
sinon j'ai pas cherché de suite de nombre qui maximise ce test
 

Reply

Marsh Posté le 26-03-2005 à 23:55:09    

fra0 a écrit :

c'est pas mon genre  :non:  


 
ok, je veut bien le croire, mais alors va falloir m'expliquer une petite chose... ton code (là je parle du premier qui est le plus rapide) fait 13 cycles d'horloge sur un P3 (10 sur un P4)
 
si je prends exactement l'équivalent dans mon code (c'est a dire le nombre aléatoire avant le traitement par la valeur maxi), ca donne :
 
mov eax,NombreAleatoire
mov ecx,eax
shl eax,3
sub eax,ecx
add eax,7
rcr ecx,3
xor eax,ecx
mov NombreAleatoire,eax
 
et ce code il fait 12 cycle d'horloge sur un P3 (10 sur un P4)
 
alors le petit truc à m'expliquer, c'est : comment un code qui à sensiblement le même nombre de cycles d'horloge peut tourner 2x plus rapidement...
 
la seule différence c'est qu'avec mon code, l'extraction par la valeur maxi doit se faire par le haut (avec une multiplication) et pas par le bas (avec une trop lente division), parceque sinon ca n'ira pas (mon code est spécialement fait pour une extraction par le haut)...

Reply

Marsh Posté le 27-03-2005 à 04:58:06    

j'aurais préféré que tu me demandes comment s'écrit getPrevRand(unsigned int*)  
 
m'enfin....
 
histoire de remettre les pendules à l'heure,
le plus rapide de mes codes est le dernier avec 5 cycles max (chez moa pour un million d'exécutions avec les mov ECX,@seed en plus et en décomptant le temps des boucles C.) j'ai mis un peu de temps mais ça faisait des lustres que j'avais pas pondu d'asm.
 
ensuite j'ai donné mes benchs avec le deuxième qui est le plus lent, mais le plus juste bien qu'il manque une instruction pour garantir sa stabilité numérique.
 
C'est une question de portée,  regarde bien :
 
en 12 cycles (fut 22) , tu génères 8 bits aléatoires.
en 10 cycles (mais on dirait bien 5 selon mon RDTSC), j'en génère 32...
 
tu vois, j'ai pris une marge de pure courtoisie pour t'éviter le seppuku.
 

Reply

Marsh Posté le 27-03-2005 à 09:31:47    

NightWare a écrit :

:heink:  ben si tu lis le code, tu remarqueras que j'ai remplacé texto la dernière division par une simple multiplication par le même chiffre (donc déjà là, je peut pas obtenir le "même" résultat qu'avec l'original).
 :wahoo:  ensuite, si tu veut savoir si la première multiplication remplace parfaitement la première division, ben la réponse est "mathèmatiquement" oui.
bref : si tu transforme la deuxième division également (c'est pas très pratique, mais c'est possible et facile à faire) et bien, tu obtiendras EXACTEMENT la même suite que la routine originelle...
 
 :D  maintenant, vu que c'est une routine qui génére des nombres aléatoires, je vois pas vraiment l'interêt d'obtenir EXACTEMENT la même suite que la routine d'origine... a moins que tu ait des besoins particuliers ???


Comme je ne connais pas l'asm, je ne peux juger.
 
Mais la raison de ma question est simple : l'algo de Park & Miller est aussi parfois appelé "Minimal Standard" pour les générateurs aléatoires. Il a été proposé parce que le rand de la librairie C d'origine est considéré comme insuffisant pour des applications de calcul. P&M a été testé avec tous les tests de vérification de générateurs aléatoires connus et est suffisamment général pour être proposé comme un générateur pseudo-alétoire standard. Quand qq utilise le Park & Miller, il s'attend à obteir exactement la même suite avec la même graine. Sinon, ce n'est pas du Park & Miller, c'est autre chose. Et ton autre chose, il doit pouvoir passer les mêmes tests, sinon il est pourri.  
Si un gars veut utiliser ton code dans son algo d'intégration par Monte-Carlo (utilisé en physique des hautes énergies) ou de cryptage à la volée (comme en télécom par ex.), il s'attend à ce que ses calculs donnent exactement les mêmes résultats qu'avant pour valider ton code, et pas qq chose "à peu près" équivalent. Autre exemple, si un fichier crypté avec un algo basé sur du Park & Miller passe par ton code qui ne donne pas la même séquence pour le décryptage, ce qui va sortir ne sera pas très digeste amha.
 
Donc si tu dis pouvoir améliorer l'algo en question, il faut que ton code donne strictement la même séquence. Sinon, tu ne l'améliores pas, tu ne fais que le modifier pour tes propres besoins (ce qui est parfaitement acceptable pour un JV, mais pas pour du calcul ou du cryptage).
 
En tout cas, si j'en crois les résultats de son test, le code de fra0 a l'air de présenter les qualités d'un bon générateur. Ce serait intéressant qu'il le passe aussi à ce crible bcp plus complet et/ou à celui-là.
 
Quelques tests de générateurs
http://paloweb.com/Computers/Algor [...] m_Numbers/


Message édité par el muchacho le 27-03-2005 à 10:38:45
Reply

Marsh Posté le 27-03-2005 à 12:50:40    

NightWare a écrit :

comment un code qui à sensiblement le même nombre de cycles d'horloge peut tourner 2x plus rapidement...


vidange de pipelines ? caches froids ?


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 27-03-2005 à 12:52:14    

nraynaud a écrit :

vidange de pipelines ? caches froids ?


parallélisation ? regroupement des lectures de mémoire et des écritures de mémoire ? (Athlon XP)


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 27-03-2005 à 13:04:56    

muchacho > attention, en crypto, on n'utilise de toutes façon jamais un générateur congruent.
 
On attrape l'entropie du lieu où génère la clef normalement.


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 29-03-2005 à 02:58:47    

pour muchacho, ok, alors voilà la manip pour obtenir exactement le même résultat (mais comme je l'ai dit, c'est pas pratique). on va prendre la valeur 100 comme exemple... donc au lieu de diviser par 100 on va multiplier par la partie entiere de 42949673,95 ((4294967295/100)+1), soit 42949673
 
arrivé ici, on a la partie extraite (la valeur sur 100) qui se trouve dans eax. malheureusement, le registre eax est devenu une fraction de 1 (le résultat après la virgule). c'est difficilement lisible (parceque pour obtenir la valeur il faudrait pratiquer une division avec un chiffre à virgule... ca c'est trop lent)
 
heureusement, il existe une petite astuce :
on a la valeur d'origine et la valeur privée de l'extraction (en edx), alors pour obtenir cette extraction (sans avoir à traiter eax)
on va multiplier edx par la valeur d'exemple (ici 100), que l'on va soustraire à la valeur d'origine
 
et... tada !!! on a exactement le même résultat que la routine d'origine...
 
le problème c'est que pour obtenir une valeur sur 100 il faudra entrer "nrandom 42949673" (c'est ça qui est pas pratique) au lieu de "nrandom 100"
 
pour vous montrer un exemple concret de cette methode, voici une macro texte qui supprime la division par 10. elle est, je crois, suffisament explicite :
 

Code :
  1. ;-------------------------------------------------------------------------
  2. ; convertir un motlong (ben ouip, je viens du monde amiga...) en texte au format décimale
  3. ; Réceptionne : les 32 bits a transformer en eax et la chaine de caractères
  4. ; Retourne : rien
  5. ; syntaxe : Convertir32bitsEnChaineDecimale [eax],[la variable texte]
  6. ;-------------------------------------------------------------------------
  7. Convertir32bitsEnChaineDecimale MACRO motlong:REQ,variable:REQ
  8. LOCAL Label1,Label2,Label3
  9.  ECHO Convertir32bitsEnChaineDecimale
  10.  push ebx      ;; empiler ebx
  11.  push ecx      ;; empiler ecx
  12.  push edx      ;; empiler edx
  13.  push esi      ;; empiler esi
  14.  push edi      ;; empiler edi
  15.  xor ecx,ecx      ;; initialiser la valeur de boucles
  16.  mov esi,OFFSET variable     ;; récuperer l'adresse de la variable
  17.  add esi,(SIZEOF variable)-2    ;; définir l'adresse réelle de départ a modifier
  18.  mov edi,429496730     ;; placer le multiplicateur 429496730 en edi
  19. Label1:  mov ebx,eax      ;; sauvegarder eax dans ebx
  20.  mul edi       ;; multiplier eax par edi (429496730)
  21.  mov eax,edx      ;; placer le dépassement obtenu en edx dans eax
  22.  shl edx,2      ;; ) multiplier edx par 10 et laisser le résultat en edx
  23.  add edx,eax      ;; )
  24.  shl edx,1      ;; )
  25.  sub ebx,edx      ;; soustraire edx à ebx
  26.  add ebx,"0"      ;; ajouter le caractère de base
  27.  mov BYTE PTR [esi],bl     ;; sauvegarde du caractére
  28.  dec esi       ;; décrementer l'adresse de la variable
  29.  inc ecx       ;; incrementer la boucle
  30.  cmp ecx,SIZEOF variable     ;; comparer le compteur à SIZEOF variable
  31.  jl Label1      ;; si inférieur continuer a definir la chaine (Label 1)
  32.  mov esi,OFFSET variable     ;; ) correction des erreurs générées qui apparaissent
  33.  add esi,(SIZEOF variable)-2    ;; ) sur des très gros nombre finissant par 7,8 et 9
  34. Label2:  cmp BYTE PTR [esi],"0"     ;; )
  35.  jge Label3      ;; )
  36.  add BYTE PTR [esi],10     ;; )
  37.  dec esi       ;; )
  38.  dec BYTE PTR [esi]     ;; )
  39.  jmp Label2      ;; )
  40. Label3:
  41.  pop edi       ;; désempiler edi
  42.  pop esi       ;; désempiler esi
  43.  pop edx       ;; désempiler edx
  44.  pop ecx       ;; désempiler ecx
  45.  pop ebx       ;; désempiler ebx
  46. ENDM


 
ok, alors je suppose que les dernières lignes de la macros (concernant la correction des erreurs) vous interpellent, alors
je vais vous fournir une petite explication. si l'on essaye d'afficher une valeur importante finissant par 79, 88, 89, 97, 98, 99
(exemple "22222222889" on obtiendra "22222222289/" ). ce n'est pas une erreur ! (ca correspond à 222222222890 -1, c'est donc bien le bon nombre), c'est juste une fluctuation (de 3 et des cahuetes... si je me souviens bien) qui apparait lorsqu'on traite le nombre d'origine par tranches...
 
c'est un tout petit inconvénient (qui apparait sur peu de nombre), c'est vite réglé. par contre le gain obtenu déchire grave (puisque la division se repéte 11 fois pour un 32 bits)...
 
pour harkonnen et nraynaud, vos hypothèses sont intéressantes, mais elles seraient valables uniquement si le test avait été fait sur des machines différentes, ou si le traitement avait été pratiqué dans des conditions différentes... or là, ca à été fait sur la même machine et, à priori, dans les mêmes conditions, d'où ma question...
 
pour fra0, ben on peut pas dire que ta reponse est très sensée... tu dis :

fra0 a écrit :

en 12 cycles (fut 22) , tu génères 8 bits aléatoires.
en 10 cycles (mais on dirait bien 5 selon mon RDTSC), j'en génère 32...


or là, il y a un petit problème... je génére bien 8 bits (15 bits aléatoires en fait, puisque je me sert des bits de poids faible poou genérer les 15 bits de poids fort aléatoires) mais ces 8 bits (là, tu prends la routine complète) comprennent l'extraction de la valeur désirée (2, 50, 100, etc... et pas uniquement 8 bits, vu que ca peut aller jusqu'a 32767 si on veut)
 
aussi, à tes 32 bits générés tu ne crois pas qu'il faudrait appliquer le traitement correspondant (l'extraction) si tu veut réellement comparer... ce que tu as fait c'est comparer une routine complète (comprennant l'extraction de la valeur désirée) à une routine générant seulement 32 bits aléatoires... tu trouves ca normal ?
 
si tu veut comparer ok, mais alors compare exactement ce qui peut l'être ! et pas ce qui t'arrange... donc si tu veut comparer ben compare avec le code de mon post précédant, qui LUI correspondrai exactement au tiens dans le processus (c'est a dire l'aléatoire avant extraction, je sais ! les 32 bits ne sont pas tous aléatoires, mais j'ai jamais prétendu le contraire). 2x plus rapide... bha bien sûr...

Reply

Marsh Posté le 29-03-2005 à 05:51:14    

c'est un ordre de grandeur,
 
mais t'aurais du dire tout de suite que tu venais de l'amiga,
 
je génère un produit de 64bits, entre un nombre de 32bits et une constante de 24 - 31 bits
 
je produis le résultat en jetant (empiriquement) les 16 bits du haut (d'EDX) et les 16 bits du bas (d'EAX)
 
puis en recombinant le reste, j'obtiens 32 bits aléatoires
 
ensuite retourner une valeur entre [0 et N[ n'est plus vraiment le rôle d'un générateur,
ça dépend plutôt de ta façon d'interpréter les bits en tant que programmeur :
un appel suffit à générer 8 nombres entre 0 et 16 par exemple...
alors, la génération des séquences devient négligeable (en plus de gagner en période) devant le temps de converison des valeurs,
ça pose un tout autre problème (aussi rébarbatif que sans issue heureusement).
 
sinon,
en doublant le vecteur d'état de mon générateur (2 DWORDS) j'ai fini par arriver à 4 cycles (3.6!!) avec une version qui mystifie complètement ENT et passe le DieHard de Marsaglia sans accrocs.

Reply

Marsh Posté le 02-04-2005 à 01:21:30    

:sweat:  pour la réponse à muchacho, 2 petites rectifications :
1° après la manip il faudrait, en fait, entrer nrandom 42949673,100 (he oui... il faudra aussi entrer la valeur multiplicatrice... ce qui est encore moins pratique...)
2° ce n'est pas 11 mais 10 divisions qui sont escamotées par la macro texte...
 

fra0 a écrit :

mais t'aurais du dire tout de suite que tu venais de l'amiga,


pourquoi ? c'est pas vraiment important, ca fait plus d'une dizaine d'années que j'y ai plus touché, pourtant je continu a appeler un 32bits un longword au lieu d'un doubleword... comme quoi il y a des trucs tenaces dans l'esprit humain...
 
j'avais décidé de ne pas me lancer dans la prog sur pc (plus par dépit du sort réservé à l'amiga qu'autre chose dailleurs), mais comme j'ai énormément de temps devant moi en ce moment, ben j'ai quand même recommencé il y a quelques semaines... c'est plus fort que moi...  
 

fra0 a écrit :

je génère un produit de 64bits, entre un nombre de 32bits et une constante de 24 - 31 bits
je produis le résultat en jetant (empiriquement) les 16 bits du haut (d'EDX) et les 16 bits du bas (d'EAX)
puis en recombinant le reste, j'obtiens 32 bits aléatoires


t'es sympa, mais j'avais quand même capté le code, ben ouaip... quand même...  ;) . au fait vu qu'on parle de ce code là, avec la valeur 9357421 c'est bon, mais avec la valeur 7421, le nombre maxi que j'obtiens avec une extraction par le haut de 1000 (pour avoir 0<x<1000) est 113... donc il y a des bits qui ne sont jamais positionnés (c'était juste pour info).
 

fra0 a écrit :

ensuite retourner une valeur entre [0 et N[ n'est plus vraiment le rôle d'un générateur,
ça dépend plutôt de ta façon d'interpréter les bits en tant que programmeur


là je comprends pas tout, je dois dire... quelques questions m'assaillent... aie !!! alors je vais les poser, c'est parti mon kiki... (heu... c'est une expression, je n'ai rien à voir avec le marquis de sade...). je vois bien l'interêt d'obtenir un nombre aléatoire limité, ou encore contenu dans une certaine tranche... mais quel est l'interêt de générer des valeurs 32 bits ? ce que je veut dire, c'est que les 32 bits devront de toute manière être traiter, a un moment ou a un autre, non ? et, si on extrait des valeurs plus tard ce sera plus lent, non ? (sauf si on extrait des valeurs 2^x, mais c'est pas très pratique, on ne code plus comme ça, si ?). ou il y a un truc que j'ai pas capté ? ou alors ca a une utilité pour du cryptage ou un truc du genre ?
 
tellement de temps est passé... que j'ai encore une autre question, qui est nettement plus importante à mes yeux... je suis pas devenu hasbeen au point de devoir intégrer une emission de tv reality sur tf1 quand même..., si ?
 
si c'est " :(  si !" appuyez sur le 1, si c'est " :ange:  heu... mais non... mais non..." appuyez sur le 2.  :bounce:  ce vote vous a couté $$$ euros, merci pour votre vote

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed