RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х. Он определяется рекуррентным соотношением:
V j + 1 ≡ ( 65539 V j ) mod 2 31 {displaystyle V_{j+1}equiv (65539V_{j})mod 2^{31}}где V 0 {displaystyle V_{0}} нечётное.
Псевдослучайные числа вычисляются следующим образом:
X j ≡ V j / 2 31 {displaystyle X_{j}equiv V_{j}/2^{31}}Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 2 .
Основанием для выбора параметров генератора послужило то, что в рамках целочисленной 32-битной машинной арифметики операции по модулю 2 31 {displaystyle 2^{31}} , в частности, умножение произвольного числа на 65539 = 2 16 + 3 {displaystyle 65539=2^{16}+3} , выполняются эффективно. В то же время такой выбор обладает и принципиальным недостатком. Рассмотрим следующее выражение (будем полагать, что все операции выполняются по модулю 2 31 {displaystyle 2^{31}} ):
x k + 2 = ( 2 16 + 3 ) x k + 1 = ( 2 16 + 3 ) 2 x k {displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k}}откуда, раскрыв квадратичный сомножитель, получаем:
x k + 2 = ( 2 32 + 6 ⋅ 2 16 + 9 ) x k = [ 6 ⋅ ( 2 16 + 3 ) − 9 ] x k {displaystyle x_{k+2}=(2^{32}+6cdot 2^{16}+9)x_{k}=[6cdot (2^{16}+3)-9]x_{k}}что, в свою очередь, показывает наличие линейной зависимости (а следовательно, и полной корреляции) между тремя соседними элементами последовательности:
x k + 2 = 6 x k + 1 − 9 x k {displaystyle x_{k+2}=6x_{k+1}-9x_{k}}Как следствие корреляции, точки в трёхмерном пространстве, координаты которых получены по данному алгоритму, располагаются на сравнительно небольшом количестве плоскостей (в приведённом примере — на 15 плоскостях).
Пример
Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении V 0 = 1 {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.