я нахожу это

Трехмерный график из 100 000 значений, созданный с помощью RANDU. Каждая точка представляет собой 3 последовательных псевдослучайных значения. Хорошо видно, что точки лежат в 15 двумерных плоскостях .

я нахожу это — линейный конгруэнтный генератор псевдослучайных чисел (LCG) типа Парка-Миллера , который использовался преимущественно в 1960-х и 1970-х годах. Это определяется повторением :

$V_{j+1}=65539\cdot V_{j}\,{\bmod {\,}}2^{31}\,$

с начальным номером семени, $V_{0}$ как нечетное число . Он генерирует псевдослучайные целые числа $V_{j}$ которые равномерно распределены в интервале [1, 2 ³¹ − 1] , но в практических приложениях часто преобразуются в псевдослучайные рациональные числа. $X_{j}$ в интервале (0, 1) по формуле:

$X_{j}={\frac {V_{j}}{2^{31}}}$.

IBM RANDU широко считается одним из самых непродуманных генераторов случайных чисел, когда-либо созданных. как «поистине ужасный» и был описан Дональдом Кнутом . Как будет видно ниже, он плохо проходит спектральный тест для размерностей больше 2.

Причиной выбора именно этих значений множителя и модуля было то, что при 32-битном целочисленном размере слова арифметика по модулю 2 ³¹ и $65539$ $({\text{i.e., }}2^{16}+3)$ расчеты можно было выполнять быстро, используя аппаратные побитовые операторы , но значения были выбраны для удобства вычислений, а не для статистического качества.

Проблемы с множителем и модулем

Для любого линейного конгруэнтного генератора с модулем m, используемого для генерации точек в n - мерном пространстве, точки попадают не более чем в $(n!\times m)^{1/n}$ параллельные гиперплоскости. Это указывает на то, что низкомодульные LCG не подходят для многомерного моделирования Монте-Карло . Для m = 2^31 и n = 3 LCG может иметь до 2344 плоскостей, теоретический максимум. В той же статье Марсальи доказано, что гораздо более точная верхняя оценка представляет собой сумму абсолютных значений всех коэффициентов гиперплоскостей в стандартной форме. То есть, если гиперплоскости имеют вид Ax1 + Bx2 + Cx3 = некоторое целое число, например 0, 1, 2 и т. д., то максимальное количество плоскостей равно |A|+|B|+|C|.

Теперь исследуем значения множителя 65539 и модуля 2. ³¹ выбран для RANDU. Рассмотрим следующий расчет, в котором каждый член следует брать по модулю 2. ³¹ . Начните с написания рекурсивного отношения как:

$x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k}\,$

который после расширения квадратичного множителя становится:

$x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}\,$

потому что 2 ³² против 2 ³¹ = 0

и позволяет нам показать корреляцию между тремя точками как:

$x_{k+2}=6x_{k+1}-9x_{k}\,$

Суммируя абсолютные значения коэффициентов, мы получаем не более 16 плоскостей в 3D, а при ближайшем рассмотрении становимся всего 15 плоскостями, как показано на схеме выше. Даже по стандартам LCG это показывает, что RANDU ужасен: использование RANDU для выборки единичного куба позволит выбрать только 15 параллельных плоскостей, что даже близко не соответствует верхнему пределу $\left\lfloor (2^{31}\times 3!)^{1/3}\right\rfloor =2344$ самолеты.

В результате широкого использования RANDU в начале 1970-х годов многие результаты того времени кажутся подозрительными. Такое нарушение поведения было обнаружено еще в 1963 году. на 36-битном компьютере и тщательно переопределен на 32-битной IBM System/360 . Считалось, что к началу 1990-х годов его подвергли массовой чистке. но даже в 1999 году компиляторы FORTRAN все еще использовали его.

Пример вывода

Начало периода вывода RANDU для начального начального числа. $V_{0}=1$ является:

1, 65539, 393225, 1769499, 7077969, 26542323, … (последовательность A096555 в OEIS )

Внешние ссылки

• Цитаты, связанные с RANDU, в Wikiquote