RANDU

thumb|Распределение в трёхмерном пространстве 100 000 точек, полученных алгоритмом RANDU. Можно видеть, что точки расположены на 15 [[Плоскость (математика)|плоскостях.]] RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х годах. Он определяется рекуррентным соотношением : $V\_\{j+1\}\; \backslash equiv\; (65539\; V\_j)\; \backslash bmod\; 2^\{31\},$ где $V\_0$ нечётное.

Псевдослучайные числа, равномерно распределены в диапазоне(периоде последовательности) [1, 2³¹ − 1], но из-за короткого периода, данный алгоритм лучше использовать для генерации последовательностей из (0, 1), полученных посредством следующей формулы: : $X\_j\; \backslash 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\; \backslash cdot\; 2^\{16\}\; +\; 9)\; x\_k\; =\; [6\; \backslash cdot\; (2^\{16\}\; +\; 3)\; -\; 9]\; x\_k,$

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

: $x\_\{k+2\}\; =\; 6x\_\{k+1\}\; -\; 9x\_k.$

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