RANDU

Распределение в трёхмерном пространстве 100 000 точек, полученных алгоритмом RANDU. Можно видеть, что точки расположены на 15 плоскостях.

RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х годах. Он определяется рекуррентным соотношением

$V_{j+1}\equiv (65539V_j){mod2}^{31},$

где $V_0$ нечётное.

Псевдослучайные числа, равномерно распределены в диапазоне(периоде последовательности) [1, 2³¹ − 1], но из-за короткого периода, данный алгоритм лучше использовать для генерации последовательностей из (0, 1), полученных посредством следующей формулы:

$X_j\equiv V_j/2^{31}.$

Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 2.

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

$x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3{)}^2{x}_k,$

откуда, раскрыв квадратичный сомножитель, получаем

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

что, в свою очередь, показывает наличие линейной зависимости (а следовательно, и полной корреляции) между тремя соседними элементами последовательности:

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

Как следствие корреляции, точки в трёхмерном пространстве, координаты которых получены по данному алгоритму, располагаются на сравнительно небольшом количестве плоскостей (в приведённом примере — на 15 плоскостях).

Пример

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении $V_0=1$:

            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 году он использовался в некоторых компиляторах Фортрана.

Цитаты

Шаблон:Начало цитаты Само его название — RANDU (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах! Шаблон:Oq Шаблон:Конец цитаты Шаблон:Начало цитаты Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 11 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять. Шаблон:Oq Шаблон:Конец цитаты

Дополнительная литература

• М. Максимов. Случайны ли «случайные» числа? — Журнал «Наука и жизнь», № 10, 1986, С. 112—113.

Ссылки

• RANDU random number generator fails 3D+ spectral tests Шаблон:Wayback