RANDU

Распределение в трёхмерном пространстве 100 000 точек, полученных алгоритмом RANDU. Можно видеть, что точки расположены на 15 плоскостях.

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

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

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

Псевдослучайные числа, равномерно распределены в диапазоне(периоде последовательности) [1, 2³¹ − 1], но из-за короткого периода, данный алгоритм лучше использовать для генерации последовательностей из (0, 1), полученных посредством следующей формулы:

${\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 в начале 1970-х годов, полученные в это время результы могут находиться под подозрением^[4]. Проблема была замечена уже в 1963^[5] на 36-битном компьютере. Считалось, что к началу 1990-х алгоритм был выведен из употребления,^[6] но ещё в 1999 году он использовался в некоторых компиляторах Фортрана^[7].

Цитаты

Само его название — RANDU (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах!^[8]

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

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

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

Примечания

1. Peter Young. Randu: a bad random number generator (англ.). Physics 115/242 (24 апреля 2013). Дата обращения: 11 сентября 2017. Архивировано 22 декабря 2018 года.
2. RANDU: the bad random number generator (англ.). GitHub (16 февраля 2016). Дата обращения: 11 сентября 2017. Архивировано 31 июля 2016 года.
3. George Marsaglia. Random Numbers Fall Mainly in the Planes (англ.) // Proc National Academy of Sciences : журнал. — сентябрь 1968. — Vol. 61, no. 1. — P. 25—28. — PMC 285899. Архивировано 1 августа 2013 года.
4. Press, William H. Numerical Recipes in Fortran 77: The Art of Scientific Computing. — 2nd. — 1992. — ISBN 0-521-43064-X.
5. Greenberger, Martin (1 марта 1965). "Method in randomness". Commun. ACM. 8 (3): 177–179. doi:10.1145/363791.363827. ISSN 0001-0782.
6. Donald Knuth – Computer Literacy Bookshops Interview  (неопр.) (7 декабря 1993). Архивировано из оригинала 28 марта 2022 года.
7. Compaq Fortran Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999 (formerly DIGITAL Fortran and DEC Fortran 90).
8. Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: «Вильямс», 2007. — Т. 2. Получисленные алгоритмы. — С. 129—130. — 832 с. — ISBN 5-8459-0081-6 (русс.) ISBN 0-201-89684-2 (англ.).
9. Donald E. Knuth. The Art of Computer Programming. — 3rd ed. — Boston: Addison-Wesley, 1998. — Т. 2. Seminumerical Algorithms.
10. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0-521-43108-5.

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

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

Ссылки

• RANDU random number generator fails 3D+ spectral tests Архивная копия от 19 ноября 2020 на Wayback Machine