WikiSort.ru - Не сортированное

В этой статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. Утверждения, не подкреплённые источниками, могут быть поставлены под сомнение и удалены. Вы можете улучшить статью, внеся более точные указания на источники.

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]

Пример

Пример псевдослучайной последовательности, порождаемой алгоритмом 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 (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах!^[4]

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

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

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

Примечания

Дополнительная литература

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

Ссылки

• RANDU random number generator fails 3D+ spectral tests