Эволюция генераторов случайных чисел

Эволюциягенераторовслучайныхчисел

предыдущий пост показал, что биты простых степеней выглядят как бы хаотично. Когда вы наносите их на график, они образуют треугольную форму, потому что размер чисел увеличивается. Числа растут геометрически, поэтому их двоичные представления растут линейно. Вот сюжет для степеней 5:

bits of powers of 5 plotted

Вы можете обрезать треугольник, так что вы видите только его прямоугольную часть, все выглядит менее правильным. Если мы посмотрим на степень p по модулю 2, скажем, 2 64 , затем мы отрезаем левую сторону треугольника.

Предположим, мы не начинаем с 1, а начинаем с другого число, назовите его семенем и каждый раз умножайте на 5. Получим ли мы хаотичный узор? Да, и мы только что изобрели генератор конгруэнтных случайных чисел . Эти ГСЧ имеют вид

x n + 1 = топор п мод м

ГСЧ, который мы неявно описали выше, будет иметь a = 5 и m = 2 128 . Это не лучший выбор из a и m , но это кое-что. Мы можем использовать разные значения множителя и модуля, чтобы получить достойный ГСЧ.

RANDU генератор случайных чисел, обычно используемый в 1960, используется a = 65539 и m = 2 32 . Оказалось, что у него заведомо плохие статистические свойства. Мы можем увидеть это с небольшой модификацией кода, используемого для построения графика выше.

 def out (s): s = s.replace ('1', chr (0x 48271 )) s = s.replace ('0', '') print (s) a, m = 65539, 2 31 x = 7 для i в диапазоне (32): x = a x% ms = format (x, '64 б ') выход (ы) 

Вот сюжет.

plotting bits of RANDU random number generator

Рисунок справа выглядит как рулон пленки. Это показывает, что биты самого низкого порядка очень регулярны. Вы также можете видеть, что нам нужно начать с большого семени: начиная с 7, мы создали большие треугольные отверстия в верхней части изображения. На изображении есть и другие закономерности, которые трудно описать, но вы чувствуете, что что-то не так, особенно когда вы сравниваете это изображение с лучшей альтернативой.

Намного лучший выбор параметры – множитель a = 48271 и модуль m = 2 64 -1. Это параметры в генераторе случайных чисел MINSTD . Вот график его битов, также начинающийся с семени 7.

plot of MINSTD bits

Генератор MINSTD намного лучше, чем RANDU, и подходит для некоторых приложений, но далек от современного. Вы могли бы добиться большего, если бы использовали гораздо больший множитель и модуль упругости порядка 2 128 или 2 128 .

Вы могли бы сделать еще лучше, добавив шаг перестановки в свой конгруэнтный генератор. Это идея PCG ( преобразованный конгруэнтный генератор ) семейство генераторов случайных чисел. Эти генераторы безупречно проходят все стандартные статистические тесты.

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

Похожие сообщения