RANDU

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

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

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

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

${\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]