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

 
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 ?

 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 :
 

 
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...

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

sinon y'a ça aussi, en plus sexy et 100% FPU

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

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

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 ?

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

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

nope

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

c'est toujours interressant ce genre de trucs.

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é   )

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é.

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) ?

 
   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).
   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...
 
   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)

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

 
   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).
 

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...

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
 

 
ou sur 32...
 

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

 
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é ?

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  

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
...

edit : double post

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."

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

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

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

 
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 ?    
 

c'est pas mon genre    
 
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  

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

 
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    
 

 
eheh
 

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
 

 
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)...

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.
 

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/

vidange de pipelines ? caches froids ?

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

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.

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 :
 

 
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 :

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...

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.

 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...
 

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...  
 

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).
 

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 "  heu... mais non... mais non..." appuyez sur le 2.    ce vote vous a couté $$$ euros, merci pour votre vote