RANDU

RANDU — это один из первых линейных конгруэнтных генераторов псевдослучайных чисел (ЛКГ), разработанный в 1960-х годах корпорацией IBM и широко применявшийся в научных и инженерных расчётах на мэйнфреймах IBM System/360. Генератор известен своей крайне низкой статистической качественностью, что привело к многочисленным ошибкам в результатах моделирования, особенно в задачах многомерной статистики и методом Монте-Карло. RANDU стал классическим примером того, как неправильный выбор параметров линейного конгруэнтного генератора может привести к катастрофическим корреляциям в выходной последовательности.

История

Разработка RANDU была частью усилий IBM по созданию стандартной библиотеки математических подпрограмм для новой линейки мэйнфреймов System/360, выпущенной в 1964 году. Генератор был включён в состав пакета Scientific Subroutine Package (SSP), который поставлялся вместе с операционной системой. Разработчики стремились к простоте реализации и высокой скорости работы, а не к статистической надёжности. В то время теория псевдослучайных чисел ещё только формировалась, и последствия выбора неудачных параметров не были полностью осознаны.

RANDU использовался в течение нескольких десятилетий, вплоть до 1980-х годов, во многих научных и инженерных программах, включая расчёты в физике, химии, экономике и военном моделировании. Критика генератора началась после публикации работ Джорджа Марсальи в начале 1970-х годов, который показал, что точки, сгенерированные RANDU, лежат на небольшом количестве плоскостей в трёхмерном пространстве. Это привело к тому, что многие исследователи, использовавшие RANDU, получили некорректные результаты, особенно в задачах, требующих равномерного распределения точек в многомерных пространствах.

Алгоритм

RANDU является линейным конгруэнтным генератором, работающим по формуле:

\[ X_{n+1} = (a \cdot X_n + c) \mod m \]

где:

• \( a = 65539 \) — множитель,
• \( c = 0 \) — приращение (нулевое, что делает генератор мультипликативным),
• \( m = 2^{31} \) — модуль.

Начальное значение \( X_0 \) (зерно) задаётся пользователем и обычно является нечётным целым числом. Выходное псевдослучайное число \( U_n \) в диапазоне \([0, 1)\) получается делением \( X_n \) на \( m \).

Выбор параметров

Выбор множителя \( a = 65539 \) был обусловлен соображениями эффективности на 32-битных компьютерах: \( 65539 = 2^{16} + 3 \), что позволяло реализовать умножение с помощью сдвигов и сложений, минуя аппаратное умножение. Однако этот выбор оказался фатальным для статистического качества. Модуль \( m = 2^{31} \) был выбран как максимальное значение, помещающееся в 32-битное знаковое целое число.

Статистические недостатки

Основная проблема RANDU заключается в сильной корреляции между последовательными числами, особенно в трёхмерном пространстве. Анализ показывает, что все точки, сгенерированные RANDU, лежат на 15 плоскостях в трёхмерном пространстве. Это означает, что при использовании трёх последовательных чисел для задания координат точки в трёхмерном пространстве, все такие точки будут находиться на этих плоскостях, что делает распределение крайне неравномерным и неслучайным.

Математическое обоснование

Для линейного конгруэнтного генератора с модулем \( m = 2^k \) и множителем \( a \), точки \( (X_n, X_{n+1}, X_{n+2}) \) лежат на плоскостях, задаваемых уравнением:

\[ a^2 \cdot X_n - (a+1) \cdot X_{n+1} + X_{n+2} \equiv 0 \pmod{2^k} \]

Для RANDU с \( a = 65539 \) это уравнение упрощается до:

\[ 65539^2 \cdot X_n - 65540 \cdot X_{n+1} + X_{n+2} \equiv 0 \pmod{2^{31}} \]

Поскольку \( 65539^2 \equiv 6 \pmod{2^{31}} \) (что можно проверить), получаем:

\[ 6 \cdot X_n - 65540 \cdot X_{n+1} + X_{n+2} \equiv 0 \pmod{2^{31}} \]

Это линейное уравнение показывает, что все тройки последовательных чисел лежат на одной из 15 плоскостей, а не распределены равномерно по всему кубу \([0, 1)^3\). Количество плоскостей определяется как \( \sqrt[3]{m} \approx 1290 \), но из-за выбора множителя их число сокращается до 15.

Другие проблемы

• Короткий период для младших битов: Младшие биты \( X_n \) имеют гораздо меньший период, чем старшие. Например, младший бит (чётность) имеет период всего 2, что делает RANDU непригодным для задач, требующих случайности на уровне отдельных битов.
• Отсутствие равномерности в одномерном случае: Хотя одномерное распределение RANDU формально равномерно, оно страдает от автокорреляции, что проявляется в тестах на частоту и серийных тестах.
• Неустойчивость к тестам: RANDU проваливает практически все современные статистические тесты на случайность, включая тест на спектр, тест на тройки и тест на сферы.

Последствия использования

Использование RANDU привело к многочисленным ошибкам в научных публикациях и инженерных расчётах. Наиболее известный пример — работы в области физики плазмы и статистической механики, где RANDU использовался для моделирования методом Монте-Карло. В 1970-х годах было обнаружено, что многие результаты, полученные с помощью RANDU, невоспроизводимы и не соответствуют физической реальности. Это привело к пересмотру многих научных работ и к разработке более качественных генераторов, таких как RANMAR, RANLUX и Mersenne Twister.

В образовательной сфере RANDU часто используется как пример того, как не следует проектировать генераторы псевдослучайных чисел. Его изучение входит в курсы по численным методам и компьютерному моделированию в университетах.

Критика и наследие

RANDU подвергся резкой критике со стороны сообщества вычислительной математики. Джордж Марсалья, один из ведущих экспертов в области генерации случайных чисел, назвал RANDU «одним из самых ужасных генераторов, когда-либо использовавшихся» (англ. "one of the most dreadful generators ever used"). В своей книге «Random Numbers for Computers» (1985) он подробно описал недостатки RANDU и предложил альтернативы.

Несмотря на свою порочность, RANDU сыграл важную роль в развитии теории псевдослучайных чисел. Он стимулировал разработку более строгих критериев оценки качества генераторов, таких как тест на спектр и тест на корреляцию. Современные генераторы, такие как Mersenne Twister (1997) и PCG (2014), проходят все известные статистические тесты и не имеют подобных дефектов.

Интересные факты

• RANDU был настолько широко распространён, что его влияние можно проследить в некоторых старых программных пакетах, которые до сих пор используются в некоторых отраслях.
• В 1990-х годах, с развитием персональных компьютеров, RANDU был заменён на более качественные генераторы, встроенные в языки программирования, такие как C (rand() с использованием LCG с параметрами из BSD) и Fortran.
• В некоторых учебниках по численным методам RANDU приводится как пример «плохого» генератора, а его параметры (a=65539, c=0, m=2^31) запоминаются студентами как «золотой стандарт того, как не надо делать».

Источники

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
• Marsaglia, G. (1968). "Random Numbers Fall Mainly in the Planes". Proceedings of the National Academy of Sciences, 61(1), 25–28.
• Marsaglia, G. (1985). Random Numbers for Computers. Unpublished manuscript.
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.
• IBM Corporation (1968). System/360 Scientific Subroutine Package (SSP) Programmer's Manual.