46 votes

.NET Framework : Le générateur de nombres aléatoires produit un motif répétitif

EDIT : Ce n'est pas un doublon, et ce n'est pas le résultat d'une mauvaise compréhension naïve de la façon d'utiliser un générateur de nombres aléatoires. Merci.

Il semble que j'ai découvert un modèle répétitif dans les nombres générés par la classe System.Random. J'utilise une instance aléatoire "maître" pour générer une graine pour une seconde instance aléatoire "principale". Les valeurs produites par cette instance aléatoire principale présentent un modèle répétitif. En particulier, le troisième nombre produit est très prévisible.

Le programme ci-dessous démontre le problème. Notez qu'une valeur d'amorçage différente est utilisée à chaque fois dans la boucle.

using System;

class Program
{
    static void Main(string[] args)
    {
            // repeat experiment with different master RNGs
        for (int iMaster = 0; iMaster < 30; ++iMaster)
        {
                // create master RNG
            var rngMaster = new Random(iMaster + OFFSET);

                // obtain seed from master RNG
            var seed = rngMaster.Next();

                // create main RNG from seed
            var rngMain = new Random(seed);

                // print 3rd number generated by main RNG
            var ignore0 = rngMain.Next(LIMIT);
            var ignore1 = rngMain.Next(LIMIT);
            var randomNumber = rngMain.Next(LIMIT);
            Console.WriteLine(randomNumber);
        }
    }

    const int OFFSET = 0;
    const int LIMIT = 200;
}

Je pense que cela devrait produire une sortie aléatoire, mais la sortie réelle sur ma boîte est :

84
84
84
84
84
84
84
84
84
84
84
...

Quelqu'un peut-il expliquer ce qui se passe ici ? La modification des constantes OFFSET et LIMIT change la valeur de sortie, mais elle se répète toujours.

53voto

Scott Chamberlain Points 32782

Bienvenue dans le monde des RNG non cryptographiquement forts. Apparemment, le RNG intégré de .NET a tendance à produire le troisième nombre 84 si vous le limitez à 0 à 200 pour ses sorties. Jetez un coup d'oeil à la version suivante du programme, elle montre mieux ce qui se passe dans la sortie.

class Program
{
    static void Main(string[] args)
    {
        Console.WindowWidth = 44;
        Console.WindowHeight = 33;
        Console.BufferWidth = Console.WindowWidth;
        Console.BufferHeight = Console.WindowHeight;

        string template = "|{0,-5}|{1,-11}|{2,-5}|{3,-5}|{4,-5}|{5,-5}|";
        Console.WriteLine(template, "s1", "s2", "out1", "out2", "out3", "out4");
        Console.WriteLine(template, new String('-', 5), new String('-', 11), new String('-', 5), new String('-', 5), new String('-', 5), new String('-', 5));

        // repeat experiment with different master RNGs
        for (int iMaster = 0; iMaster < 30; ++iMaster)
        {
            int s1 = iMaster + OFFSET;
            // create master RNG
            var rngMaster = new Random(s1);

            // obtain seed from master RNG
            var s2 = rngMaster.Next();

            // create main RNG from seed
            var rngMain = new Random(s2);

            var out1 = rngMain.Next(LIMIT);
            var out2 = rngMain.Next(LIMIT);
            var out3 = rngMain.Next(LIMIT);
            var out4 = rngMain.Next(LIMIT);
            Console.WriteLine(template, s1, s2, out1, out2, out3, out4);
        }

        Console.ReadLine();
    }

    const int OFFSET = 0;
    const int LIMIT = 200;
}

Voici le résultat

|s1   |s2         |out1 |out2 |out3 |out4 |
|-----|-----------|-----|-----|-----|-----|
|0    |1559595546 |170  |184  |84   |84   |
|1    |534011718  |56   |177  |84   |123  |
|2    |1655911537 |142  |171  |84   |161  |
|3    |630327709  |28   |164  |84   |199  |
|4    |1752227528 |114  |157  |84   |37   |
|5    |726643700  |0    |150  |84   |75   |
|6    |1848543519 |86   |143  |84   |113  |
|7    |822959691  |172  |136  |84   |151  |
|8    |1944859510 |58   |129  |84   |189  |
|9    |919275682  |144  |122  |84   |28   |
|10   |2041175501 |30   |115  |84   |66   |
|11   |1015591673 |116  |108  |84   |104  |
|12   |2137491492 |2    |102  |84   |142  |
|13   |1111907664 |88   |95   |84   |180  |
|14   |86323836   |174  |88   |84   |18   |
|15   |1208223655 |60   |81   |84   |56   |
|16   |182639827  |146  |74   |84   |94   |
|17   |1304539646 |31   |67   |84   |133  |
|18   |278955818  |117  |60   |84   |171  |
|19   |1400855637 |3    |53   |84   |9    |
|20   |375271809  |89   |46   |84   |47   |
|21   |1497171628 |175  |40   |84   |85   |
|22   |471587800  |61   |33   |84   |123  |
|23   |1593487619 |147  |26   |84   |161  |
|24   |567903791  |33   |19   |84   |199  |
|25   |1689803610 |119  |12   |84   |38   |
|26   |664219782  |5    |5    |84   |76   |
|27   |1786119601 |91   |198  |84   |114  |
|28   |760535773  |177  |191  |84   |152  |
|29   |1882435592 |63   |184  |84   |190  |

Il existe donc de fortes corrélations entre la première sortie du RND maître et les premières sorties d'un second RNG qui a été enchaîné sur le premier. Le site Random Le RNG n'est pas conçu pour être "sûr", il est conçu pour être "rapide", donc des choses comme ce que vous voyez ici sont le compromis entre la rapidité et la sécurité. Si vous ne voulez pas que de telles choses se produisent, vous devez utiliser un générateur de nombres aléatoires sécurisé sur le plan cryptographique.

Cependant, il ne suffit pas de passer à un générateur de nombres aléatoires cryptographiques (CRNG), il faut aussi faire attention à la manière dont on utilise le CRNG. Un problème très similaire s'est produit avec la sécurité sans fil WEP. En fonction de l'IV indiqué dans l'en-tête, il était possible de prédire la valeur de la graine (la clé WEP) du générateur de nombres aléatoires utilisé pour protéger la connexion. Bien qu'ils aient utilisé un CRNG (ils ont utilisé RC4), ils ne l'ont pas utilisé correctement (vous devez cracher quelques 1000 itérations avant que la sortie ne devienne non prévisible).

3voto

Bob Bryan Points 1312

Après avoir exécuté le code moi-même, il semble que la valeur renvoyée pour le 3ème élément - indépendamment de la graine est un assez mauvais défaut. J'ai modifié votre code comme suit pour le rendre un peu plus flexible :

public static void TestRNG()
{
    const int OFFSET = 0;
    const int LIMIT = 200;
    const int RndCount = 50;
    const int FieldsPerLine = 10;
    int Rnd;
    for (int iMaster = 0; iMaster < RndCount; ++iMaster)
    {
        // create master RNG
        var rngMaster = new Random(iMaster + OFFSET);

        // obtain seed from master RNG
        var seed = rngMaster.Next();

        // create main RNG from seed
        var rngMain = new Random(seed);

        // print 3rd number generated by main RNG
        Console.WriteLine();
        for (int Loop = 0; Loop < FieldsPerLine; Loop++)
        {
            Rnd = rngMain.Next(LIMIT);
            Console.Write(Rnd.ToString().PadLeft(3) + " ");
        }
    }
}

Le résultat ressemble à ceci :

170 184  84  84   5 104 164 113 181 147
 56 177  84 123 150 132 149  56 142  88
142 171  84 161  94 160 134 199 102  28
 28 164  84 199  39 189 119 141  62 168
114 157  84  37 184  17 105  84  23 108
  0 150  84  75 129  45  90  27 183  48
 86 143  84 113  74  74  75 169 144 188
172 136  84 151  18 102  60 112 104 129
 58 129  84 189 163 130  46  55  64  69
144 122  84  28 108 159  31 197  25   9
 30 115  84  66  53 187  16 140 185 149
116 108  84 104 198  15   1  82 145  89
  2 102  84 142 142  44 186  25 106  29
 88  95  84 180  87  72 172 168  66 170
174  88  84  18  32 100 157 110  26 110
 60  81  84  56 177 129 142  53 187  50
146  74  84  94 121 157 127 196 147 190
 31  67  84 133  66 185 113 138 108 130
117  60  84 171  11  14  98  81  68  70
  3  53  84   9 156  42  83  24  28  11
 89  46  84  47 101  70  68 166 189 151
175  40  84  85  45  99  54 109 149  91
 61  33  84 123 190 127  39  51 109  31
147  26  84 161 135 155  24 194  70 171
 33  19  84 199  80 184   9 137  30 112
119  12  84  38  25  12 195  79 190  52
  5   5  84  76 169  40 180  22 151 192
 91 198  84 114 114  69 165 165 111 132
177 191  84 152  59  97 150 107  71  72
 63 184  84 190   4 125 136  50  32  12
149 177  84  28 148 154 121 193 192 153
 35 171  84  66  93 182 106 135 153  93
121 164  84 104  38  10  91  78 113  33
  7 157  84 143 183  39  77  20  73 173
 93 150  84 181 128  67  62 163  34 113
179 143  84  19  72  95  47 106 194  53
 65 136  84  57  17 124  32  48 154 194
151 129  84  95 162 152  18 191 115 134
 37 122  84 133 107 180   3 134  75  74
123 115  84 171  52   9 188  76  35  14
  9 108  84  10 196  37 173  19 196 154
 95 102  84  48 141  65 158 162 156  95
181  95  84  86  86  94 144 104 117  35
 66  88  84 124  31 122 129  47  77 175
152  81  84 162 176 150 114 189  37 115
 38  74  84   0 120 179  99 132 198  55
124  67  84  38  65   7  85  75 158 195
 10  60  84  76  10  35  70  17 118 136
 96  53  84 115 155  64  55 160  79  76
182  46  84 153  99  92  40 103  39  16

Par le passé, j'ai vu des exemples de code qui n'utilisaient pas les 3 ou 4 premières valeurs renvoyées par la méthode Random.Next. Je sais maintenant pourquoi. Donc, une solution simple serait de jeter les 4 premières valeurs retournées par la méthode Random.Next.

Si vous êtes intéressé par un générateur de nombres aléatoires très rapide qui produit également des nombres aléatoires de haute qualité, alors consultez le site Projet TinyMT - que j'ai porté à partir du code C original.

1voto

Mark Hurd Points 4746

C'est à peine plus qu'un commentaire, mais il faut de l'espace. J'ai ajouté manuellement l'indentation et les commentaires au code DotLisp dans la zone de texte SO uniquement. Le code est identique, à l'exception de l'utilisation ou non de l'option (.Next (Random. i)) comme graine, ou s'il utilise simplement le i que la graine elle-même, et qu'elle vérifie le troisième ou le quatrième .Next aléatoire.

Je n'ai pas vérifié à nouveau maintenant, mais je crois que chaque .Next x récupère toujours un nouvel échantillon et convertit ce résultat en quelque chose entre 0 y x-1 .

Utilisation de x = (* 15 183) = 2745 est venu parce que regarder des gammes plus petites et plus comme 10000 les graines, j'ai trouvé la troisième .Next x était aléatoire "uniforme", mais avec deux taux d'"uniforme" ; la plus petite gamme de valeurs moins choisies était d'environ 177 à 190 nombres contigus. (Vous pouvez voir cela en appelant (print-histo h) dans la dernière ligne, mais réduisez le nombre de graines testées :-) ) Lorsque j'ai augmenté le nombre de graines, j'ai augmenté cette plage.

Le code accumule simplement un compte pour chaque .Next x et affiche le nombre de ces comptages. Pour un vrai hasard uniforme .Next x cela devrait produire une belle courbe en cloche, comme on le voit dans le dernier cas (quatrième .Next , graines séquentielles).

(let (h (Hashtable.))
 (dotimes i 6553600
  (lets
   (s (.Next (Random. i))
    r (Random. s)) ; using random seed
   (dotimes j 2 r.Next) ; skipping 2 results
   (let (x (r.Next (* 15 183)))
    (x h (+ 1 (or (x h) 0))))))
 (print-histo (histo h.Values)))

  1 2368
  3 2369
 11 2370
 20 2371
 11 2372
 12 2373
 17 2374
 15 2375
  8 2376
 13 2377
 20 2378
 11 2379
  3 2380
  8 2382
 94 2383
253 2384
296 2385
240 2386
248 2387
238 2388
233 2389
252 2390
236 2391
321 2392
163 2393
 18 2394

Une courbe en cloche asymétrique et une autre petite courbe en cloche plate ou simplement une queue très peu uniforme.

(let (h (Hashtable.))
 (dotimes i 6553600
  (lets
   (s (.Next (Random. i))
    r (Random. s)) ; using random seed
   (dotimes j 3 r.Next) ; skipping 3 results
   (let (x (r.Next (* 15 183)))
    (x h (+ 1 (or (x h) 0))))))
 (print-histo (histo h.Values)))

 11 2377
 43 2378
 90 2379
114 2380
138 2381
133 2382
132 2383
143 2384
127 2385
147 2386
130 2387
136 2388
145 2389
223 2390
430 2391
354 2392
177 2393
 72 2394

Deux courbes en cloche avec l'une large et l'autre étroite.

(let (h (Hashtable.))
 (dotimes i 6553600
  (let (r (Random. i)) ; using sequential seed
   (dotimes j 2 r.Next) ; skipping 2 results
   (let (x (r.Next (* 15 183)))
    (x h (+ 1 (or (x h) 0))))))
  (print-histo (histo h.Values)))

 12 2380
104 2381
143 2382
123 2383
106 2384
 55 2385
115 2386
387 2387
511 2388
537 2389
454 2390
194 2391
  4 2392

En fait, deux courbes en cloche.

(let (h (Hashtable.))
 (dotimes i 6553600
  (let (r (Random. i)) ; using sequential seed
   (dotimes j 3 r.Next) ; skipping 3 results
   (let (x (r.Next (* 15 183)))
   (x h (+ 1 (or (x h) 0))))))
 (print-histo (histo h.Values)))

 18 2384
154 2385
432 2386
758 2387
798 2388
477 2389
105 2390
  3 2391

Enfin une simple courbe en cloche.

En résumé, il semble qu'il y ait deux problèmes distincts : le troisième échantillon n'est pas très uniforme en général et les graines produites par le premier échantillon accentuent le problème ou présentent un problème distinct.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X