Меню
Главная
Случайная статья
Настройки
|
RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х годах. Он определяется рекуррентным соотношением
где нечётное.
Псевдослучайные числа, равномерно распределены в диапазоне(периоде последовательности) [1, 231 1], но из-за короткого периода, данный алгоритм лучше использовать для генерации последовательностей из (0, 1), полученных посредством следующей формулы:
Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных, так как он не проходит спектральный тест при количестве измерений, превышающем 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 в начале 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 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять.
Примечания
- Peter Young. Randu: a bad random number generator (англ.). Physics 115/242 (24 апреля 2013). Дата обращения: 11 сентября 2017. Архивировано 22 декабря 2018 года.
- RANDU: the bad random number generator (англ.). GitHub (16 февраля 2016). Дата обращения: 11 сентября 2017. Архивировано 31 июля 2016 года.
- 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 года.
- Press, William H. Numerical Recipes in Fortran 77: The Art of Scientific Computing. — 2nd. — 1992. — ISBN 0-521-43064-X.
- Greenberger, Martin (1 марта 1965). Method in randomness. Commun. ACM. 8 (3): 177–179. doi:10.1145/363791.363827. ISSN 0001-0782.
- Donald Knuth – Computer Literacy Bookshops Interview (неопр.) (7 декабря 1993). Архивировано из оригинала 28 марта 2022 года.
- Compaq Fortran Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999 (formerly DIGITAL Fortran and DEC Fortran 90).
-
-
-
Дополнительная литература
Ссылки
|
|