.NET Framework: генератор случайных чисел создает повторяющийся шаблон

EDIT: это не дубликат, и это не результат наивного непонимания использования генератора случайных чисел. Спасибо.

Кажется, я обнаружил повторяющийся шаблон в числах, сгенерированных классом System.Random. Я использую "мастер" случайный экземпляр для генерации семени для второго "основного" случайного экземпляра. Значения, полученные в этом основном случайном экземпляре, имеют повторяющийся шаблон. В частности, произведенное 3-е число очень предсказуемо.

В приведенной ниже программе показана проблема. Обратите внимание, что каждое другое значение используется каждый раз через цикл.

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;
}

Я думаю, что это должно произвести произвольный вывод, но фактический вывод на моем ящике:

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

Может ли кто-нибудь объяснить, что здесь происходит? Изменение констант OFFSET и LIMIT изменяет выходное значение, но оно всегда повторяется.

Ответы

Ответ 1

Добро пожаловать в мир не криптографически сильных ГСЧ. По-видимому, встроенный RNG.NET имеет тенденцию делать 3-й номер, который он выдает 84, если вы ограничиваете его на 0 до 200 для своих выходов. Взгляните на следующую версию программы, она показывает больше того, что происходит на выходе.

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;
}

Вот вывод

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

Таким образом, существуют некоторые сильные корреляции между первым выходом основного RND и первыми несколькими выходами второго RNG, который был скован первым. Random RNG не предназначен для "безопасного", он разработан как "быстрый", поэтому такие вещи, как то, что вы видите здесь, являются компромиссами между быстрым и безопасным. Если вам не нужны такие вещи, вам нужно использовать криптографически безопасный генератор случайных чисел.

Однако просто переключение на криптографический генератор случайных чисел (CRNG) недостаточно, вам все равно нужно быть осторожным, как вы используете CRNG. Очень похожая проблема произошла с беспроводной безопасностью WEP. В зависимости от того, что было указано в заголовке, можно было предсказать, какое значение для начального значения (ключ WEP) для генератора случайных чисел использовалось для защиты соединения. Хотя они использовали CRNG (они использовали RC4), они не использовали его правильно (вам нужно выплюнуть несколько 1000 итераций, прежде чем выход станет не предсказуемым).

Ответ 2

После запуска кода он выглядит как возвращаемое значение для третьего элемента - независимо от того, что семя является довольно плохим недостатком. Я изменил ваш код следующим образом, чтобы сделать его немного более гибким:

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) + " ");
        }
    }
}

Результат выглядит следующим образом:

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

В прошлом я видел примеры кода, которые не используют первые 3 или 4 значения, возвращаемые методом Random.Next. Теперь я знаю, почему. Таким образом, простая работа заключается в том, чтобы выбросить первые 4 значения, возвращенные методом Random.Next.

Если вас интересует очень быстрый генератор случайных чисел, который также производит высококачественные случайные числа, тогда просмотрите проект TinyMT - который я портирован из исходного кода C.

Ответ 3

Это всего лишь комментарий, но ему нужно пространство. Я вручную добавил отступы и комментарии к коду DotLisp только в текстовом поле SO. Код идентичен, за исключением того, использует ли он (.Next (Random. i)) как семя, или просто использует i как само семя и проверяет ли он третий или четвертый случайный случай .Next.

Я не проверял снова прямо сейчас, но я считаю, что каждый .Next x всегда извлекает один новый образец и преобразует результат в нечто между 0 и x-1.

Использование x = (* 15 183) = 2745 произошло потому, что, глядя на меньшие диапазоны и больше похожие на семена 10000, я обнаружил, что третий .Next x был "равномерным" случайным, но с двумя скоростями "равномерности"; меньший диапазон меньших выбранных значений составлял от 177 до 190 смежных чисел. (Вы можете увидеть это, вызвав (print-histo h) в последней строке, но уменьшите количество тестируемых семян:-)) Когда я увеличил количество семян, я увеличил этот диапазон.

Код просто накапливает счетчик для каждого результата .Next x и отображает счетчик этих счетчиков. Для истинного равномерного случайного .Next x это должно привести к хорошей кривой колокола, как видно из последнего случая (четвертый .Next, последовательные семена).

(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

Скошенная кривая колокола и еще одна небольшая плоская кривая колокола или просто очень неравномерный хвост.

(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

Две кривые колокола с одной широкой и одной узкой.

(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

Эффективно две кривые колокола.

(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

Наконец, простая кривая колокола.

В целом, похоже, что существуют два отдельных вопроса: третий образец не очень однородный вообще, а семена, созданные в первом образце, либо подчеркивают проблему, либо показывают отдельную проблему.