RANDU

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

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

где нечётное.

Псевдослучайные числа вычисляются следующим образом:

Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 2[1] [2].

Основанием для выбора параметров генератора послужило то, что в рамках целочисленной 32-битной машинной арифметики операции по модулю , в частности, умножение произвольного числа на , выполняются эффективно. В то же время такой выбор обладает и принципиальным недостатком. Рассмотрим следующее выражение (будем полагать, что все операции выполняются по модулю ):

откуда, раскрыв квадратичный сомножитель, получаем:

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

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

Пример

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении :

            1
        65539
       393225
      1769499
      7077969
     26542323
     95552217
    334432395
   1146624417
   1722371299
     14608041
          ...
    134633675
   1893599841
   1559961379
    907304297
   2141591611
    388843697
    238606867
     79531577
    477211307
            1

Цитаты

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

Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 11 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять.

Примечания

  1. Peter Young. Randu: a bad random number generator. Physics 115/242 (April 24, 2013).
  2. RANDU: the bad random number generator. GitHub (16 Feb 2016). Дата обращения: 11 сентября 2017.
  3. George Marsaglia. Random Numbers Fall Mainly in the Planes // Proc National Academy of Sciences : журнал. — сентябрь 1968. Т. 61, № 1. С. 25—28.
  4. Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования = The Art of Computer Programming. — 3-е изд. М.: «Вильямс», 2007. — Т. 2. Получисленные алгоритмы. — С. 129—130. — 832 с. — ISBN 5-8459-0081-6 (русс.) ISBN 0-201-89684-2 (англ.).
  5. Donald E. Knuth. The Art of Computer Programming. — 3rd ed. — Boston: Addison-Wesley, 1998. — Т. 2. Seminumerical Algorithms.
  6. 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.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.