Показать меню

RANDU

24.09.2021
21

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.

Еще по этой теме:
Число Уомерсли
16:00, 09 сентябрь
Число Уомерсли
Число Уомерсли (Wo или α) — критерий подобия в гидродинамике, определяющий соотношение между темпом пульсации потока жидкости и её вязкостью. Оно определяется следующим образом:
Порядок числа по модулю
20:08, 18 декабрь
Порядок числа по модулю
Показателем, или мультипликативным порядком, целого числа a {displaystyle a} по модулю m {displaystyle m}
Эйлеровы числа
05:09, 18 декабрь
Эйлеровы числа
Эйлеровы числа (или числа Эйлера) — целые числа E 0 , E 1
Цепь Каннингема
11:22, 17 декабрь
Цепь Каннингема
Цепь Каннингема (цепь почти удвоенных чисел) — последовательность простых чисел определённого вида, названо в честь математика Алана Каннингема. Цепь Каннингема первого рода длины n — это
Алгебраическая теория чисел
14:00, 08 декабрь
Алгебраическая теория чисел
Алгебраическая теория чисел — раздел теории чисел, основная задача которого — изучение свойств целых элементов числовых полей. В алгебраической теории чисел понятие числа расширяется, в качестве
Максимальный тор
12:52, 03 декабрь
Максимальный тор
Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: