RANDU

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (20 апреля 2015)

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

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

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

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

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

Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 2^[1][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 плоскостях).^[3]

Пример псевдослучайной последовательности, порождаемой алгоритмом 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 в начале 1970-х годов, полученные в это время результы могут находиться под подозрением^[4]. Проблема была замечена уже в 1963^[5] на 36-битном компьютере. Считалось, что к началу 1990-х алгоритм был выведен из употребления,^[6] но ещё в 1999 году он использовался в некоторых компиляторах Фортрана^[7].

Само его название — RANDU (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах!^[8]

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

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

Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 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]

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

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