GÉNÉRATEUR DE NOMBRES PSEUDO-ALÉATOIRES
cs_Forman
Messages postés
600
Date d'inscription
samedi 8 juin 2002
Statut
Membre
Dernière intervention
6 avril 2010
-
3 juil. 2009 à 11:21
Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 - 5 janv. 2010 à 13:14
Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 - 5 janv. 2010 à 13:14
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/50254-generateur-de-nombres-pseudo-aleatoires
https://codes-sources.commentcamarche.net/source/50254-generateur-de-nombres-pseudo-aleatoires
5 janv. 2010 à 13:14
Cordialement, Bacterius !
5 janv. 2010 à 13:02
4 janv. 2010 à 23:38
A mon avis c'est une erreur de l'AV
A plus
Excuses
4 janv. 2010 à 23:34
Cordialement, Bacterius !
4 janv. 2010 à 22:54
Possible ??
10 août 2009 à 14:58
randomize : E = H(Int64(GetTickCount, @randomize)).
random : renvoie de façon itérative chacun des 16 nombres de E. Dès que l'on est à court de nombres, on effectue E = H(E). De cette façon, même si l'on tombe sur des suites qui se répètent, il faudrait pour rentrer dans un état de "boucle", avoir une suite de 16 nombres bien placés (c.a.d. où le premier nombre de la suite correspond au premier nombre de E). Qu'en penses-tu Forman ?
Cordialement, Bacterius !
Cordialement, Bacterius !
3 août 2009 à 12:14
Init seed => Seed = H(Seed) => Utilisation des 16 cardinals du hash => Seed = H(Seed) => ...
Ce qui fait que :
- la période minimale est de 16
- la période maximale peut atteindre 2^512 :o
- aucun risque de "boucles", l'algorithme est conçu pour ! Et comme l'initialisation se fait sur un nombre de 64 bits (et non plus 32) ... enfin voilà.
Cordialement, Bacterius !
29 juil. 2009 à 18:18
Et ... oui il existe des tables aléatoires sur le web, de plusieurs dizaines de gigaoctets (je crois en avoir vu une "soi-disant" de 1 téra dans une publicité).
Cordialement, Bacterius !
29 juil. 2009 à 18:04
29 juil. 2009 à 17:23
Mais pour les méthodes de Monte-Carlo ça me paraît difficile à mettre en oeuvre, puisqu'il faut généralement plusieurs dizaines de milliards de nombres aléatoires pour obtenir un résultat probant.
Mais dans ce cas, on peut utiliser un fichier (généralement, on a plus d'espace disque que de mémoire). Je m'explique : au lancement du programme, on crée un fichier contenant, disons ... hmm ... cinq milliards (5.000.000.000) de nombres. Ca nous fait un fichier de 5.000.000.000 * 4 octets = 18 gigas. Bon ... c'est long à calculer mais on gagnera largement ce temps par la suite.
Ensuite, lors du calcul de Monte-Carlo, on va prendre les nombres par blocs de 128 mégas, soit 33554432 nombres, et faire notre calcul.
Et comme le calcul des 5 milliards de nombres est super long, on pourrait réutiliser ce fichier pour générer d'autres nombres, en appliquant une formule mathématique simple. Je m'explique encore : on génère nos 5 milliards de nombres, puis lorsqu'on utilise cet énorme fichier, on applique à chaque nombre du fichier la transformation suivante : Nombre + X (où X est une valeur unique au processus, typiquement GetTickCount).
Ca pourrait être intéressant comme source, ça ...
Cordialement, Bacterius !
29 juil. 2009 à 16:53
Mais on peut faire encore plus simple:
-déclarer un tableau TabRandom de 54*30=1620 éléments (ou plus!)
-dans la partie initialization, lancer FillArray:
procedure FillArray
var
a:Integer;
begin
for a:=Low(TabRandom) to High(TabRandom) do
TabRandom[a]:=MyRandomFunction();
end;
-déclarer une variable RandomIndex de type Integer (initialisée à zéro).
-redéclarer la procédure randomize (par exemple en utilisant l'heure courante):
procedure Randomize();
begin
RandomIndex:=Low(TabRandom)+((GetTickCount div 100) mod (High(TabRandom)-Low(TabRandom)+1));
end;
-redéclarer la fonction Random:
function Random: Integer;
begin
Result:=TabRandom[RandomIndex];
Inc(RandomIndex);
if RandomIndex=High(TabRandom) then
RandomIndex:=Low(TabIndex);
end;
Les valeurs de la fonction MyRandomFunction sont calculées une fois pour toute lors de l'initialisation, donc même si c'est une fonction compliquée qui prend du temps à s'exécuter ça ne ralentira pas le prog par la suite. C'est le même principe que les tables de Cosinus par exemple.
Il y a plusieurs intérêts d'utiliser quelque chose de semblable:
-on peut utiliser une fonction MyRandomFunction complexe avec un cahier des charges plus évolué que la fonction Random de base (par exemple, qui garantit qu'on ne tire jamais 2 fois de suite la même valeur, ou toute autre contrainte statistique) sans que ça rame par la suite
-il est possible de donner un ID à la partie: la première valeur prise par RandomIndex lors de l'utilisation de Randomize. Ainsi, on peut rejouer une partie avec la même suite du générateur aléatoire.
Il faut toutefois choisir une valeur assez élevée pour la taille du tableau TabRandom qui soit compatible avec le type d'application qu'on souhaite faire. Par exemple, si tu veux qu'il y ait en gros 30 parties possibles pour un jeu de carte alors effectivement 30*54 parait adapté. Pour une méthode de calcul de type Monte Carlo ça ne sera vraisemblablement pas assez et il faudrait augmenter la taille (typiquement à une valeur du même ordre que le nombre de tirages, tout en restant dans une utilisation raisonnable de la mémoire).
29 juil. 2009 à 16:25
Cordialement, Bacterius !
3 juil. 2009 à 16:55
L'avantage c'est que lire un élément du tableau peut être plus rapide que de calculer un random avec un algo sophistiqué.
3 juil. 2009 à 16:47
Cordialement, Bacterius !
3 juil. 2009 à 16:45
3 juil. 2009 à 16:21
Mais je ne comprends pas très bien l'avant-dernier paragraphe : si on reprend toujours le même tableau en le parcourant d'une façon linéaire, on tombera toujours sur la même séquence, et donc lors d'un nouveau tirage on aura exactement le même jeu ?
Cordialement, Bacterius !
3 juil. 2009 à 16:14
Tout générateur déterministe (entendre par là dont le prochain état est codable un certains nombre de bits) est forcément périodique. Dans ton cas je peux t'affirmer sans faire aucun test qu'il y a au moins une boucle de longueur au plus 2^32 (soit 4 milliard environ :-) ... Tout simplement parce que ta graine est stockée sur 32 bits.
Dans ton exemple avec 54 cartes, effectivement un tel générateur serait raisonnablement efficace.
Mais je pense que dans ce cas, il faut précalculer une séquence: faire un tableau d'environ 54 entiers, stoker une séquence aléatoire dedans au lancement du programme (avec randomize avant) puis définir une nouvelle fonction random qui renvoie successivement tous les éléments du tableau en revenant au début quand la fin est atteinte.
Pourquoi? Tout simplement parce que ça prend moins de temps de renvoyer le n-ième élément d'un tableau que de calculer un hash, faire des xor, etc... pour un résultat "statistiquement équivalent".
3 juil. 2009 à 15:53
Cordialement, Bacterius !
3 juil. 2009 à 15:51
Cordialement, Bacterius !
3 juil. 2009 à 15:48
Effectivement si tu sais qu'une période de longueur N est acceptable alors si ton code fait au moins aussi bien c'est OK. Après il faut aussi regarder la répartition statistique des éléments des boucles (vérifier que c'est en gros uniforme dans l'intervalle).
Ce qui fait la difficulté de trouver des bons générateurs, c'est que pour une longueur de boucle minimale imposée, il doit aussi être très rapide à calculer. En ce sens les générateurs arithmétiques avec des modulo (comme celui de Borland) est un bon compromis...
3 juil. 2009 à 15:39
Mais au-delà de 16 répétitions ça prend un temps monstrueux.
Le problème pour chercher les boucles c'est qu'il faut faire un compromis entre mémoire et vitesse. Il est possible d'aller un plus vite pour chercher une longue boucle en fixant une grande quantité de mémoire.
3 juil. 2009 à 15:33
Cordialement, Bacterius !
3 juil. 2009 à 15:13
Seed := H.A xor H.B xor H.C xor H.D;
Maintenant l'important serait de voir si l'on peut obtenir des périodes de longueur supérieure à X (où X est la quantité de nombres aléatoires requis pour une tâche quelconque), je pense.
Cordialement, Bacterius !
3 juil. 2009 à 15:11
--------------------------------------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
a,p:LongWord;
b,c,d:Integer;
begin
if Started then
Exit;
Stopped:=False;
Started:=True;
try
p:=$1000000 div ((MAX_TAB+1)*(MAX_TAB+2));
a:=Seed0 mod p;
repeat
Inc(a);
if a=p then begin
a:=0;
Caption:=Format('Initial seed = %u',[Seed0]);
Application.ProcessMessages;
if Stopped then
Break;
end;
Seed:=Seed0;
Inc(Seed0);
b:=1;
Tab[0]:=Seed;
repeat
Random;
c:=0;
while (Tab[c]<Seed) and (c1);
Tab[b]:=Seed;
Memo1.Lines.Add(Format('Loop detected (Length = %u):',[b]));
for c:=0 to b do
Memo1.Lines.Add(Format('Seed(%u)=%u',[c,Tab[c]]));
Memo1.Lines.Add('');
Break;
end;
for d:=b downto c do
Tab[d]:=Tab[d-1];
Tab[c]:=Seed;
Inc(b);
until b>MAX_TAB;
until Seed0=High(LongWord);
finally
Started:=False;
end;
end;
--------------------------------------------------------------------------------
Et quelques résultats:
Loop detected (Length = 11):
Seed(0)=1576860536
Seed(1)=1243888324
Seed(2)=133932042
Seed(3)=3917576848
Seed(4)=1486399104
Seed(5)=1549541129
Seed(6)=1460177290
Seed(7)=4272665070
Seed(8)=1426530670
Seed(9)=1949176323
Seed(10)=3781238255
Seed(11)=1576860536
Loop detected (Length = 10):
Seed(0)=357440169
Seed(1)=2637825466
Seed(2)=826517477
Seed(3)=1427081938
Seed(4)=1610603249
Seed(5)=1231174083
Seed(6)=3321287677
Seed(7)=252121279
Seed(8)=1190741914
Seed(9)=1231279339
Seed(10)=357440169
Loop detected (Length = 3):
Seed(0)=1108601366
Seed(1)=563960130
Seed(2)=2017111036
Seed(3)=1108601366
3 juil. 2009 à 14:47
J'ai fait des essais avec la fonction que tu as postée en recherchant des boucles de longueur au plus 16 et j'ai trouvé plusieurs boucles de longueur 2 (j'ai fait varier la seed initiale entre 0 et un milliard et j'ai calculé les 8 permières valeurs):
Loop detected (Length = 2):
Seed(1)=1576860536
Seed(2)=1243888324
Loop detected (Length = 2):
Seed(1)=1460177290
Seed(2)=4272665070
Loop detected (Length = 2):
Seed(1)=357440169
Seed(2)=2637825466
Loop detected (Length = 2):
Seed(1)=1610603249
Seed(2)=1231174083
Loop detected (Length = 2):
Seed(1)=1190741914
Seed(2)=1231279339
Ca signifie que si jamais la graine atteint l'une de ces valeurs ton générateur va osciller entre les 2 valeurs.
Si tu veux tester voici le source qui recherche les boucles. Il faut 2 boutons sur une fiche, l'un "start" l'autre "stop" et un mémo pour l'affichage des résultats.
Pour chercher des boucles plus longues il faut augmenter la valeur de MAX_TAB.
--------------------------------------------------------------------------------
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, LEA_hash, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
private
{ Private declarations }
public
{ Public declarations }
Started,Stopped:Boolean;
end;
var
Form1: TForm1;
implementation
const
MAX_TAB=$F;
var
Seed: Longword;
Seed0: LongWord=0;
Tab:array[0..MAX_TAB] of Longword;
procedure randomize;
begin
Seed := GetTickCount; { On se base sur le temps machine }
end;
procedure Random;
Var
H: THash;
begin
H := Hash(Seed, 4); { On récupère le hash de la valeur actuelle du générateur }
Seed := H.A + H.B + H.C + H.D; { On attribue à la valeur actuelle la somme des entiers du hash }
end;
{$R *.dfm}
{ TForm1 }
procedure TForm1.Button1Click(Sender: TObject);
var
a,p:LongWord;
b,c,d:Integer;
begin
if Started then
Exit;
Stopped:=False;
Started:=True;
p:=$1000000 div ((MAX_TAB+1)*(MAX_TAB+2));
a:=Seed0 mod p;
try
repeat
Inc(a);
if a=p then begin
a:=0;
Caption:=Format('Initial seed = %u',[Seed0]);
Application.ProcessMessages;
if Stopped then
Break;
end;
Seed:=Seed0;
Inc(Seed0);
b:=1;
Tab[0]:=Seed;
repeat
Random;
c:=0;
while (Tab[c]<Seed) and (cTab[0]) and (b>1);
Memo1.Lines.Add(Format('Loop detected (Length = %u):',[b]));
for c:=0 to b-1 do
Memo1.Lines.Add(Format('Seed(%u)=%u',[c+1,Tab[c]]));
Memo1.Lines.Add('');
Break;
end;
for d:=b downto c do
Tab[d]:=Tab[d-1];
Tab[c]:=Seed;
Inc(b);
until b>MAX_TAB;
until Seed0=High(LongWord);
finally
Started:=False;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Stopped:=True;
end;
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
Stopped:=True;
end;
end.
--------------------------------------------------------------------------------
3 juil. 2009 à 13:52
1. On initialise, V est égal à quelque chose (temps machine).
2. On appelle random.
Pour des raisons de clarté, notons W la valeur de V avant qu'elle ne passe au hash.
On a alors V = H(W);
Et le nombre aléatoire R = V mod Intervalle;
3. On réappelle random.
On a alors H(W) = H(H(W));
Or il a été prouvé que le hash d'un hash est unique (puisque le premier hash est unique). Ainsi la période de n'importe-quel nombre est ... théoriquement infinie (enfin théoriquement puisque en pratique on se heurte au théorème des tiroirs qui dit que pour toute fonction qui associe à un ensemble A un ensemble B (et où la taille de A est supérieure à celle B), 2 éléments de A seront nécessairement associés au même élément de B).
Le problème se situe donc nécessairement au moment où l'on va tenter de condenser le hash (128 bits) dans la valeur (32 bits).
Cordialement, Bacterius !
3 juil. 2009 à 13:51
Le mieux c'est peut-être de faire des tests (calculer la plus petite longueur de boucle) et si tu as de la chance tu auras peut-être une valeur élevée.
3 juil. 2009 à 13:14
Cordialement, Bacterius !
3 juil. 2009 à 12:40
3 juil. 2009 à 12:32
Graine : 13 => 45 => 23 => 54 => 91 => 13 (! on repart sur la même suite) ?
Cordialement, Bacterius !
3 juil. 2009 à 12:16
Cordialement, Bacterius !
3 juil. 2009 à 12:14
Par exemple, sur un échantillon de 500 000 nombres :
----------- Delphi ------ LEA-RNG ------
Moyenne 249780.80 250791.29
Médiane 249797.00 251842.50
Minimum 16 10
Maximum 499986 499983
Etendue 499970 499973
Cordialement, Bacterius !
3 juil. 2009 à 12:10
Ceci dit, vu que tu génères des nombres sur 32 bits, tu peux toujours faire un prog qui essaie successivement toutes les graines (ça ne fait que quelques milliards) pour calculer la plus petite période, quitte à le faire tourner quelques heures...
3 juil. 2009 à 11:31
Cordialement, Bacterius !
3 juil. 2009 à 11:30
Pour les tests numériques j'étais en train de réfléchir à comment les faire, voir si certains nombres sortaient plusieurs fois, etc ... (c'est ça non) ?
Mais attention ce n'est pas la somme des octets du hash, c'est la somme des entiers sur 32 bits du hash. Et il doit exister une boucle récurrente comme tu le montres, donc je pense changer en quelque chose de moins linéaire que l'addition, comme un xor couplé d'une opération logique ou deux.
Cordialement, Bacterius !
3 juil. 2009 à 11:21
Qu'en est-il des performances "statistiques"? As-tu fait des tests numériques (moyenne, écart-type, moments)? Si j'ai bien compris, tu utilises une sorte de relation de récurrence de ce type:seed(n+1) somme des octets du hash de seed(n) F(seed(n))
Est-on certain que la fonction F (ici somme des octets du hash) n'a pas de point fixe? Ou même de cycles très courts? Si on imagine que F(123456)=332 et F(332)=123456 et si jamais la seed atteint la valeur 332 ça n'est plus vraiment un bon générateur...