RANDU

редактировать

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

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

V j + 1 = 65539 ⋅ V j mod 2 31 {\ displaystyle V_ {j + 1} = 65539 \ cdot V_ {j} \, {\ bmod {\,} } 2 ^ {31} \,}

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

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

X j = V j 2 31 {\ displaystyle X_ {j} = {\ frac {V_ {j}} {2 ^ {31}}}}

X_j = \ frac {V_ {j}} {2 ^ {31}}

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

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

Содержание

1 Проблемы с множителем и модулем
2 Пример вывода
3 Ссылки
4 Внешние ссылки

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

В общем, когда LCG с модулем 2 используется для создания точек (x k, x k + 1, x k + 2) в трехмерном пространстве, точки попадают в не более 2344 параллельных плоскостей, результат указывает на непригодность LCG для моделирования Монте-Карло. Выбор множителя определяет количество самолетов. Чтобы показать проблему со значениями множителя 65539 и модуля 2, выбранными для RANDU, рассмотрим следующий расчет, в котором каждый член должен быть взят по модулю 2. Начнем с записи рекурсивного отношения как:

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

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

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

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

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

потому что 2 mod 2 = 0

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

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

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

В результате этой корреляции каждая точка лежит в одной из набора параллельных плоскостей, расположенных на расстоянии 2, 15 из которых пересекаются куб 2 x 2 x 2, содержащий точки. В результате широкого использования RANDU в начале 1970-х годов многие результаты того времени считаются подозрительными.

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

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

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

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

Ссылки

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

Викицитатник содержит цитаты, связанные с: RANDU