RANDU

Файл:Randu.png

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

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

$V_{j+1}\equiv (65539V_j)mod{2}^{31}$

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

Псевдослучайные числа вычисляются следующим образом:

$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 (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах!

Оригинальный текст (англ.)

…its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists!

Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 11 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять.

Оригинальный текст (англ.)

One of us recalls producing a «random» plot with only 11 planes, and being told by his computer center’s programming consultant that he had misused the random number generator: «We guarantee that each number is random individually, but we don’t guarantee that more than one of them is random». Figure that out.

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

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

Ссылки

• RANDU random number generator fails 3D+ spectral tests Архивная копия от 19 ноября 2020 на Wayback Machine