Faut-il se méfier de la fonction Random() de Delphi ?

[Caribensila]

Bonjour,

Dans certaines circonstances particulières j'ai décelé un bug (?) de la fonction Random() de Delphi 7 et Delphi 2010.
Je vous donne ci-dessous un bout de code qui met ce bug en évidence.
J'aimerais savoir si ce bug a déjà été signalé et s'il existe aussi sur les dernières versions de Delphi, et pourquoi pas pour d'autres langages.
Existent-il des solutions, selon vous ?
Pour cela, ce serait sympa que ceux qui disposent d'autres versions essaient de le reproduire et nous retournent l'information.

LE BUG :
Dans certains cas, le générateur de nombres pseudo-aléatoires semble "éviter" certaines valeurs.
Cela semble se produire dans des suites d'appels de Random régulières et bien particulières.

CE QUE FAIT LE BENCHMARK A TESTER :
Le test consiste à "tirer" aléatoirement sur la surface d'un Bitmap avec deux méthodes différentes.
La première méthode est classique et consiste à tirer un pixel aléatoire sur toute la surface.
La deuxième méthode est destinée à réduire la discrépance des nombres pseudo-aléatoire (la dicrépance mesure de combien un ensemble de points s'écarte d'une distribution spaciale uniforme). Elle consiste à diviser la surface du Bitmap en plus petits carrés réguliers de 4x4 pixels et a "tirer" au hasard dans chaque petit carré. C'est dans ce cas que le bug se produit. En effet, après un nombre important de "tirs" (environ 200 salves), les 2 images devraient devenir complétement noires. Or ce n'est pas le cas pour l'une d'elles.

Bizarrement, ce bug ne se produit que pour certaines dimensions de Bitmap (256x256 et 512x512 par exemple, mais pas pour 128x128 ou 240x240 pixels. Il se produit aussi pour des petits carrés de 2x2 ou 8x8 pixels).
Dans cet exemple, on arrive à éviter ce bug en effectuant un appel bidon à Random() de temps en temps, mais dans d'autres cas, comment savoir si le bug est présent ou non ?

Pour Info, cette technique de faible discrépance alliée à la méthode de Monte Carlo est utilisée dans certains calculs de produits financiers exotique (titrisation) comme ceux à l'origine de la crise des subprimes survenue en 2007.
Mais qu'on se rassure, l'origine de la crise n'est pas là !


Le test est très facile a réaliser. 2 TImages AutoSize à true, 1 TButton et un TEdit sur une fiche :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var
  gShootsNb : Integer;
 
procedure TForm1.FormCreate(Sender: TObject);
  begin
  Randomize;
  Image1.Picture.Bitmap.Height := 256;
  Image1.Picture.Bitmap.Width  := 256;
  Image2.Picture.Bitmap.Height := 256;
  Image2.Picture.Bitmap.Width  := 256;
end;
 
{Génère une salve de 4096 tirs.}
procedure TForm1.bButton1Click(Sender: TObject);
  var     i,j,X,Y : Integer;
  begin
  Inc(gShootsNb);
  Edit1.Text := IntToStr(gShootsNb);
  for i := 0 to 63 do begin
    for j := 0 to 63 do begin
      {Suite quasi-aléatoire pour Image1}
      X := (i*4) + Random(4);
      Y := (j*4) + Random(4);
      //if X=0 then Random(Y); // DE-SLACHER POUR FIXER LE BUG.
      if Image1.Picture.Bitmap.Canvas.Pixels[X,Y]=clWhite
        then Image1.Picture.Bitmap.Canvas.Pixels[X,Y]:=clBlack;
      {Suite pseudo-aléatoire pour Image2}
      X := random(256);
      Y := random(256);
      if Image2.Picture.Bitmap.Canvas.Pixels[X,Y]=clWhite
        then Image2.Picture.Bitmap.Canvas.Pixels[X,Y]:=clBlack;
    end;
  end;
end;

Merci de m'avoir lu et à ceux qui feront le test pour retour d'informations.

[Paul TOTH]

Bonjour,

ce n'est pas tout à fait surprenant, la fonction Random de Delphi est assez basique, il te faut utiliser un autre générateur de nombres aléatoires si tu veux quelque chose d'efficace.

Je ne pense pas que la fonction ait changé entre D6 et XE2, tu retrouveras donc exactement le même comportement avec la même graine (RandSeed), le calcul est très simple, j'ai du retrouver le calcul pour TPW 1.5 sur un projet porté sous Delphi car il y a eu un petit changement depuis

Code :

1
2
3
4
5
6
// version TPW 1.5
function Random(x: word): word; 
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := ((RandSeed shr 16) * x + ((RandSeed and $ffff) * (x shr 16))) shr 16;
end;

je ne sais plus quel changement il y a mais c'est minime.

[tourlourou]

Je te conseille la lecture de cet excellent article : http://www.alrj.org/docs/algo/random.php et voici une autre piste de générateur à tester : http://www.phidels.com/php/forum/for...st&postid=1820 (seul le lien sur Files Save fonctionne encore)

[ShaiLeTroll]

A la limite, utilise plutôt la fonction RandomFrom qui tire au sort un élément dans un tableau lui même ayant été généré par un Random au départ !

sinon, pense que Random(X) c'est Random() * X, donc une multiplication d'un Extended par un facteur, il est possible que la nature même de l'Extended et la gestion de l'arrondi oriente la résultat vers telle ou telle valeur !

@Paul TOTH, à la lecture de ta version TPW, il semble que celle de Delphi soit plus basique !

[philnext]

Une bonne discussion sut Stackoverflow.

[Paul TOTH]

Envoyé par philnext

Une bonne discussion sut Stackoverflow.

excellent

[Caribensila]

Merci à tous pour vos contributions.
J'ai découvert tout un monde, là...

Bon ! Résultat des courses :
Comme je n'ai pas le niveau pour choisir un algo de générateur plutôt qu'un autre et encore moins pour en coder un, je vais retenir le système de tableau + RandomFrom que propose Shai ou celui du lien de Tourlourou :

Améliorer un générateur pseudo-aléatoire

On part d'une séquence pseudo-aléatoire xn. Ces nombres sont inférieurs à m (un générateur de Lehmer par exemple). On s'en sert pour remplir un tableau tab[] de k éléments de 0 à k-1.

La procédure pour générer le nombre pseudo-aléatoire suivant est alors :
calcul du xn par l'algorithme de son choix.
calcul de j = (k * xn) \ m (si k et m sont des puissances de 2, tout ça n'est que des décalages)
le nombre produit sera tab[j], et on rempli tab[j] avec le xn qu 'on a utilisé pour calculer j.
Cet algorithme en apparence tout bête est de C. Bays et S.D.Durham. La période du générateur résultant de ce mélange est la même que celle d'origine.

Le système que j'avais trouvé dans mon code initial ( tirer de temps en temps un Random(x) ) me semble pas mal non plus à priori.
Bien que rien ne garantisse sa totale efficacité, la probabilité de faire pire que mieux est très faible, il me semble...

Ce qui décidera de la méthode seront les performances sur un algo donné, je pense.

Encore merci !


PS : Et pour les sceptiques incurables, il y a toujours cette possibilité.

PPS : A quand un petit composant "hard" sur les cartes-mères renvoyant un vrai Random ?
Son brevet vaudra de l'or, non ?

[Paul TOTH]

pour avoir du Random plus efficace tu peux aussi intégrer la position de la souris dans tes calculs, car ça c'est une donnée qui a peu de chance d'être cyclique ... bon évidemment faut pas que l'utilisateur parte boire un café pendant que ton appli calcule

[Caribensila]

Envoyé par Paul TOTH

pour avoir du Random plus efficace tu peux aussi intégrer la position de la souris dans tes calculs, car ça c'est une donnée qui a peu de chance d'être cyclique ... bon évidemment faut pas que l'utilisateur parte boire un café pendant que ton appli calcule

1) Pour mes applis, ça peut le faire...

2) Mais les machines effectuant des calculs financiers ou scientifiques à base de nombres aléatoires ne disposent pas souvent de souris.

3) On ne dort jamais à La Réunion ?

[Jipété]

Bonsoir,

Je ne comprends rien à toutes ces subtilités mathématiques mais ce matin,
j'avais 5 minutes au taf, et Lazarus (0.9.30), alors je me suis dit « testons ! »

Envoyé par Caribensila

(...) En effet, après un nombre important de "tirs" (environ 200 salves), les 2 images devraient devenir complétement noires. Or ce n'est pas le cas pour l'une d'elles. (...)

Ben, après avoir rajouté 2 lignes pour chaque image dans le FormCreate, Lazarus oblige ,les 2 images sont devenues complètement noires au 190e clic (je n'ai fait qu'un essai).
Valà,

[Caribensila]

Merci Jipété.

Ce sera répété et amplifié à Thierry Laborde.

[10_GOTO_10]

Envoyé par Caribensila

PPS : A quand un petit composant "hard" sur les cartes-mères renvoyant un vrai Random ?
Son brevet vaudra de l'or, non ?

Il suffit de brancher un micro que tu met à coté du ventilateur de l'alimentation. En isolant les bits de poids faible de la carte son, on doit avoir un truc qui ne doit pas être très éloigné d'un vrai aléatoire.

J'ai jamais testé, c'est juste une idée comme ça. Et je n'ai pas breveté l'idée, on va dire que c'est dans le domaine public.

[mick605]

Mmhh non je pense pas, tu aurais un lien avec la fréquence de rotation du ventilateur ^^

[ShaiLeTroll]

Pourquoi vouloir enregistrer le ventilateur, il est bien connu que Silence génère déjà un bruit du signal, c'est bien suffisant non ?
Sinon, mettre une caméra filmant la neige d'un tube cathodique
Mince cela déjà été inventé avec des Lampas à Lave des années 70
10 GOTO 10, il y a d'autres farfelues avant nous qui y avait déjà pensé !


Tout les vrais systèmes de random utilise un bruit basé sur un ou plusieurs phénomènes naturelles !

Sérieusement, je ne crois avoir jamais utilisé un Random dans une application professionnelle, juste pour des essais !

Windows ne fournit-il pas un générateur aléatoire pour le Chiffrage ?
Voir RtlGenRandom, CryptGenRandom ... peut-être que cela permet d'obtenir des nombres aléatoires plus fiables !

J'ignore par contre comme utiliser cela pour gérer de petits nombres, en crypto, j'ai utilisé ça pour générer des clés de 128Bits !

[Caribensila]

Envoyé par ShaiLeTroll

Sérieusement, je ne crois avoir jamais utilisé un Random dans une application professionnelle, juste pour des essais !

Ben, des essais, ce sont déjà des trucs incontournables...



Je rappelle que, dans le droit français, pour qu'une idée soit brevetable, elle ne doit pas avoir été divulguée avant le dépôt du brevet.

- Le défi serait donc de créer un mouvement quelconque qui soit chaotique...
- Et le double pendule en est capable dans certains cas ! --> Voir cet article.

Ca y est ! Ce n'est plus brevetable !

[Andnotor]

Envoyé par Caribensila

Je rappelle que, dans le droit français, pour qu'une idée soit brevetable, elle ne doit pas avoir été divulguée avant le dépôt du brevet.

Je ne suis pas un pro du baro (et encore moins en droit français...)
Mais où le bas blesse est :

Premièrement, une idée est de toute façon protégée par le droit intellectuel. Ca devrait suffire à certaines compensations.

Deuxièmement: Je trouve inadmisible qu'on puisse protéger quelque chose qu'on est incapable de mettre en oeuvre, voir qui est infaisable au moment du dépôt (qui relève de la fiction). A titre d'exemple, j'ai un gars qui me demandait de prévoir certains développements en multi-touch (brevetés) parce que Windows 7 était annoncé prochainement...

Troisièmement: en pensant que les brevêts sont par pays et en suivant ton raisonnement, quelque chose qui n'a pas été breveté en premier lieu en France... ne peut plus l'être

[Caribensila]

Tu as raison, je me suis mal exprimé en parlant d'«idée».
En fait, n'est brevetable en France qu'une solution technique à un problème technique.
Mais cela correspond tout à fait au générateur de nombres aléatoires.

Ce qui peut être breveté

Ce qui ne peut pas être breveté

Les 16 étapes clés du dépôt de brevet d'invention

[Montor]

Si j'ai compris bien
Récupérer le pois faible retourné par le compteur de cycls cpu avec QueryPerformanceCounter pourrai être utiles.

[Rekin85]

Bonjour, comme la question a été posée plus haut :

Pour votre information, voici comment fonctionne le générateur d'entiers pseudo-aléatoires de Delphi 5 et 7:

I / Appel de Randomize :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
procedure      Randomize; 
var 
        systemTime : 
        record 
                wYear  : Word; 
                wMonth  : Word; 
                wDayOfWeek      : Word; 
                wDay    : Word; 
                wHour  : Word; 
                wMinute : Word; 
                wSecond : Word; 
                wMilliSeconds: Word; 
                reserved        : array [0..7] of char; 
        end; 
asm 
        LEA    EAX,systemTime 
        PUSH    EAX 
        CALL    GetSystemTime 
        MOVZX  EAX,systemTime.wHour 
        IMUL    EAX,60 
        ADD    AX,systemTime.wMinute  { sum = hours * 60 + minutes    } 
        IMUL    EAX,60 
        XOR    EDX,EDX 
        MOV    DX,systemTime.wSecond 
        ADD    EAX,EDX                { sum = sum * 60 + seconds              } 
        IMUL    EAX,1000 
        MOV    DX,systemTime.wMilliSeconds 
        ADD    EAX,EDX                { sum = sum * 1000 + milliseconds      } 
        MOV    RandSeed,EAX 
end;

Inutile de palabrer longtemps pour comprendre qu'elle lit l'heure système en millisecondes et qu'elle en sort un longword (les étapes de calculs sont explicites) qu'elle va précieusement ranger en sortie dans une variable Longword dénommée RandSeed.

II / L'appel de Random(Range) aboutit à cette toute petite routine : en entrée EAX contient le domaine de "pêche" et aura le nombre pseudo-aléatoire généré en sortie :

Code :

1
2
3
4
5
6
7
8
9
10
procedure      _RandInt; 
asm 
{    ->EAX    Range  } 
{    <-EAX    Result  } 
        IMUL    EDX,RandSeed,08088405H 
        INC    EDX 
        MOV    RandSeed,EDX 
        MUL    EDX 
        MOV    EAX,EDX 
end;

Voici ce qu'elle fait :
1/ elle multiplie La variable RandSeed par la valeur $08088405 = 134 775 813 dans le registre EDX ce qui veut dire que le résultat est modulo 32 bits. (Randseed * 134775813) mod 2^32
2/ le résultat est incrémenté : (RandSeed * 134775813) mod 2^32 + 1
3/ cette valeur obtenue est rangée dans la variable RandSeed (pour le prochain tirage ?)
4/ elle multiplie Range par cette valeur et obtient un Int64 qui vaut Range * [(RandSeed * 134775813) mod 2^32 + 1]
5/ et elle ne renvoie que la partie haute, ce qui revient à diviser par 2^32
[Range*[(RandSeed*134775813) mod 2^32 +1] div 2^32

[Montor]

j'aimerai bein que quelqu'un teste pour moi le code suivant ... pc grillé .

Code :

1
2
3
4
5
6
7
8
9
10
11
12
function Randoom(ARange:integer): Cardinal;
var
  I:integer;
  D:int64;
begin
  Result := 0;
  QueryPerformanceCounter(D); 
  for I := 0 to 7 do
   with Int64Rec(D) do 
    Result := (Result shl 3) xor Result xor Bytes[I];
  Result := Result mod ARange;
end;