GÉNÉRATEUR DE NOMBRES PSEUDO-ALÉATOIRES

Commentaire de Forman le 03/07/2009 11:21:40

L'idée est originale, mais quand tu le compares à celui de Delphi, tu compares en termes de vitesse, c'est bien ça?

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

Commentaire de Bacterius le 03/07/2009 11:31:45

Je procède aux tests statistiques dans une autre application exemple.

Cordialement, Bacterius !

Commentaire de Bacterius le 03/07/2009 12:14:48

Forman, les performances statistiques révèlent pour l'instant que Delphi et LEA-RNG sont semblables du point de vue de la moyenne, de la médiane (bonne répartition des valeurs), du minimum et du maximum.

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 !

Commentaire de Forman le 03/07/2009 12:29:11

Je voulais dire "la plus courte période", c'est à dire la plus courte suite de nombres u(i) pour 1<=i<=n telle que

F(U(i))=U(i+1) et F(U(n))=U(1)

Si tu trouves une suite très courte c'est pas bon  :)

Pour info, celui de delphi aurait une période de 2^32 (donc maximale, voir http://www.delphifr.com/forum/sujet-PERIODE-GENERATEUR-ALEATOIRE-DELPHI_1113617.aspx)

Commentaire de Forman le 03/07/2009 12:40:30

Oui c'est ça

Commentaire de Forman le 03/07/2009 13:51:43

Si tu fais disparaitre une boucle spécifique quelque part, rien ne te garantis que tu ne vas pas en créer une ailleurs...

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.

Commentaire de Forman le 03/07/2009 14:47:22

Ca n'est pas suffisant. Par exemple, la fonction identité (F(x)=x) est elle aussi une bijection (l'image d'un nombre est unique puisque c'est lui-même :-) or si tu l'utilises sur ta graine tu obtiens une suite stationnaire (toujours la même valeur) qui est la pire fonction random qu'on puisse imaginer.

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 (c<b) do
          Inc(c);
        if Tab[c]=Seed then begin
          b:=0;
          repeat
            Tab[b]:=Seed;
            Random;
            Inc(b);
          until (Seed<>Tab[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.

--------------------------------------------------------------------------------

Commentaire de Bacterius le 03/07/2009 15:13:52

Effectivement, et il y en a sûrement beaucoup d'autres au-delà de seed = 1.000.000.000 ! Je comprends bien le principe, et ça prouve bien la faiblesse de l'addition. En effet, j'ai remplacé les additions par des ou-exclusifs pour voir, et rien n'est détecté jusqu'au milliard !
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 !

Commentaire de Forman le 03/07/2009 15:39:33

Oui c'est ça.

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.

Commentaire de Bacterius le 03/07/2009 15:51:47

Mais tout ceci peut-il indiquer une eventuelle faille dans l'algorithme de hashage lui-même ? Où c'est juste une particularité (les boucles) liée aux PRNG eux-mêmes ?

Cordialement, Bacterius !

Commentaire de Forman le 03/07/2009 16:14:17

Je n'ai pas regardé l'algo de hash mais à mon avis ça n'a rien à voir.

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

Commentaire de Forman le 03/07/2009 16:45:01

Non, pas si tu fais un Randomize avant de remplir le tableau au lancement du jeu par exemple (lui-même étant basé sur l'horloge interne).

Commentaire de Forman le 03/07/2009 16:55:40

Oui c'est bien ça. Mais si ta fonction Random entre dans une boucle d'une taille à peu près égale au bout d'un certain nombre d'utilisations, ça revient au même.

L'avantage c'est que lire un élément du tableau peut être plus rapide que de calculer un random avec un algo sophistiqué.

Commentaire de Forman le 29/07/2009 16:53:47

Oui c'est à peu près ça l'idée.

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

Commentaire de Forman le 29/07/2009 18:04:38

Oui mais pour que ça vaille le coup il faut quand même que les nombres de la table générée "offline" soit utilisée plusieurs fois (sinon avec les accès disques on perdrait plus que ce qu'on a gagné). Ceci dit je crois qu'on peut télécharger des tables aléatoires sur le web.

Commentaire de Bacterius le 03/08/2009 12:14:33

Bon, amélioration. Bon j'ai déjà changé l'algorithme de hash (il devient crucial dans cette version). Maintenant, la nouveauté c'est que :

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 !

Commentaire de cmdmcmdm le 04/01/2010 22:54:57

J'ai un code d'alerte de l'antivirus au téléchargement ?

Possible ??

Commentaire de cmdmcmdm le 04/01/2010 23:38:50

C'est avec bullgard
A mon avis c'est une erreur de l'AV
A plus

Excuses