РАНДУ

Генератор псевдослучайных чисел

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

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

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

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

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

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

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

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

Для любого линейного конгруэнтного генератора с модулем m, используемого для генерации точек в n -мерном пространстве, точки попадают не более чем в параллельные гиперплоскости. ^[5] Это указывает на то, что низкомодульные LCG не подходят для высокоразмерного моделирования Монте-Карло . Для m = 2 ³¹ и n = 3 LCG может иметь до 2344 плоскостей, теоретический максимум. Гораздо более узкая верхняя граница доказана в той же статье Марсальи как сумма абсолютных значений всех коэффициентов гиперплоскостей в стандартной форме. То есть, если гиперплоскости имеют вид Ax ₁ + Bx ₂ + Cx ₃ = некоторое целое число, такое как 0, 1, 2 и т. д., то максимальное количество плоскостей равно | A | + | B | + | C |. ^[5] ${\displaystyle (n!\times m)^{1/n}}$

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

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

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

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

(потому что 2 ³² mod 2 ³¹ = 0 ) и позволяет нам показать корреляцию между тремя точками как

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

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

В результате широкого использования RANDU в начале 1970-х годов многие результаты того времени рассматриваются как подозрительные. ^[6] Это неправильное поведение уже было обнаружено в 1963 году ^[7] на 36-битном компьютере и тщательно переработано ^{[ требуется разъяснение ]} на 32-битной IBM System/360 . Считалось, что оно было широко уничтожено к началу 1990-х годов ^[8], но компиляторы FORTRAN все еще использовали его вплоть до 1999 года. ^[1]

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

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

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

Ссылки

1. Compaq Fortran Language Reference Manual (номер заказа: AA-Q66SD-TK) сентябрь 1999 г. (ранее DIGITAL Fortran и DEC Fortran 90).
2. Энтахер, Карл (июнь 2000 г.). «Коллекция классических генераторов псевдослучайных чисел с линейными структурами – расширенная версия». Архивировано из оригинала 18 ноября 2018 г.
3. Кнут Д. Э. Искусство программирования , том 2: Получисленные алгоритмы , 2-е издание. Addison-Wesley, 1981. ISBN 0-201-03822-6 . Раздел 3.3.4, стр. 104: «одного его названия RANDU достаточно, чтобы вызвать смятение в глазах и желудках многих компьютерных специалистов!» [Обширное освещение статистических тестов на неслучайность.] 
4. Кнут (1998), стр. 188. ^{[ необходима полная цитата ]}
5. Marsaglia, George (1968). «Случайные числа падают в основном в плоскостях». Proc. Natl. Acad. Sci. USA . 61 (1): 25–28. Bibcode :1968PNAS...61...25M. doi : 10.1073/pnas.61.1.25 . PMC 285899 . PMID  16591687. 
6. Пресс, Уильям Х. и др. (1992). Численные рецепты на Фортране 77: Искусство научных вычислений (2-е изд.). ISBN 0-521-43064-X.
7. Гринбергер, Мартин (1 марта 1965 г.). «Метод случайности». Commun. ACM . 8 (3): 177–179. doi :10.1145/363791.363827. ISSN  0001-0782.
8. «Дональд Кнут – Интервью с представителями книжных магазинов по компьютерной грамотности». 7 декабря 1993 г. Архивировано из оригинала 28 марта 2022 г.

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

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