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

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

где ${\displaystyle V_{0}}$ нечётное .

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

${\displaystyle X_{j}\equiv V_{j}/2^{31}}$

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

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

${\displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k}}$

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

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

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

${\displaystyle x_{k+2}=6x_{k+1}-9x_{k}}$

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

Пример

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении ${\displaystyle 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, С. 112-113.

Ссылки

• от 19 ноября 2020 на Wayback Machine