Введение
RANDU — это линейный конгруэнтный генератор псевдослучайных чисел (LCG) типа Парка — Миллера, который в основном использовался в 1960-х и 1970-х годах. Он определяется рекуррентным соотношением:
с начальным числом-зерном, которое должно быть нечётным. Он генерирует псевдослучайные целые числа, равномерно распределённые в интервале [1, 2<sup>31</sup> − 1], но на практике часто преобразуются в псевдослучайные рациональные числа в интервале (0, 1) по формуле:
RANDU от IBM широко считается одним из самых неудачных генераторов случайных чисел, когда-либо созданных, и был назван Дональдом Кнутом «действительно ужасным». Он плохо проходит спектральный тест для размерностей больше 2, как будет показано ниже. Причина выбора этих конкретных значений для множителя и модуля заключалась в том, что при 32-битной целочисленной разрядности арифметику по модулю 2<sup>31</sup> и вычисления можно было быстро выполнять с помощью побитовых операций в аппаратном обеспечении, но значения выбирались для вычислительной эффективности, а не для статистического качества.
IBM's RANDU is widely considered to be one of the most ill conceived random number generators ever designed, and was described as "truly horrible" by Donald Knuth. It fails the spectral test badly for dimensions greater than 2 as will be seen below. The reason for choosing these particular values for the multiplier and modulus had been that with a 32 bit integer word size, the arithmetic of mod 231 and calculations could be done quickly, using bitwise operators in hardware, but the values were chosen for computational convenience, not statistical quality.
Проблемы с мультипликатором и модулем
Для любого линейного конгруэнтного генератора с модулем m, используемого для генерации точек в n-мерном пространстве, точки попадают не более чем на параллельные гиперплоскости. Это указывает на то, что LCG с низким модулем не подходят для высокоразмерного моделирования методом Монте-Карло. При m = 2^31 и n = 3, LCG может иметь до 2344 плоскостей – это теоретический максимум. В той же работе Марсальи доказано, что гораздо более строгая верхняя граница равна сумме абсолютных значений всех коэффициентов гиперплоскостей в нормальной форме. То есть, если гиперплоскости имеют вид Ax1 + Bx2 + Cx3 = некоторое целое число, например, 0, 1, 2 и т.д., то максимальное количество плоскостей равно |A| + |B| + |C|. Это нежелательное поведение было обнаружено еще в 1963 году на 36-битном компьютере и тщательно воспроизведено на 32-битном IBM System/360. Считалось, что к началу 1990-х годов оно было повсеместно устранено, однако компиляторы FORTRAN продолжали использовать его вплоть до 1999 года.