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

**Caribensila** · 08/12/2011, 01h40

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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** · 08/12/2011, 05h35

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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** · 08/12/2011, 09h47

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)

**philnext** · 08/12/2011, 10h17

Une bonne discussion sut Stackoverflow.

**Paul TOTH** · 08/12/2011, 17h59

Envoyé par philnext

Une bonne discussion sut Stackoverflow.

excellent

**Caribensila** · 08/12/2011, 19h47

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 ?

**ShaiLeTroll** · 08/12/2011, 10h13

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 !

**Jipété** · 08/12/2011, 23h30

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à,