RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х годах. Он определяется рекуррентным соотношением
где нечётное.
Псевдослучайные числа, равномерно распределены в диапазоне(периоде последовательности) [1, 231 − 1], но из-за короткого периода, данный алгоритм лучше использовать для генерации последовательностей из (0, 1), полученных посредством следующей формулы:
Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 2.
Основанием для выбора параметров генератора послужило то, что в рамках целочисленной 32-битной машинной арифметики операции по модулю , в частности, умножение произвольного числа на , выполняются эффективно. В то же время такой выбор обладает и принципиальным недостатком. Рассмотрим следующее выражение (будем полагать, что все операции выполняются по модулю ):
откуда, раскрыв квадратичный сомножитель, получаем
что, в свою очередь, показывает наличие линейной зависимости (а следовательно, и полной корреляции) между тремя соседними элементами последовательности:
Как следствие корреляции, точки в трёхмерном пространстве, координаты которых получены по данному алгоритму, располагаются на сравнительно небольшом количестве плоскостей (в приведённом примере — на 15 плоскостях).
Пример Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении :
1 65539 393225 1769499 7077969 26542323 95552217 334432395 1146624417 1722371299 14608041 ... 134633675 1893599841 1559961379 907304297 2141591611 388843697 238606867 79531577 477211307 1
Использование Из-за широкого использования RANDU в начале 1970-х годов, полученные в это время результы могут находиться под подозрением. Проблема была замечена уже в 1963 на 36-битном компьютере. Считалось, что к началу 1990-х алгоритм был выведен из употребления, но ещё в 1999 году он использовался в некоторых компиляторах ФортранаCompaq Fortran Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999 (formerly DIGITAL Fortran and DEC Fortran 90)..
Цитаты
Само его название — RANDU (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах!
Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 11 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять.
Примечания
Дополнительная литература М. Максимов. Случайны ли «случайные» числа? — Журнал «Наука и жизнь», № 10, 1986, С. 112—113.
Ссылки RANDU random number generator fails 3D+ spectral tests
Категория:Генераторы псевдослучайных чисел