Из Википедии, бесплатной энциклопедии
  (Перенаправлено из ACORN PRNG )
Перейти к навигации Перейти к поиску

ЖЕЛУДЬ или " dditive Co ngruential R andom N умбра" генераторы является надежным семейством PRNGs ( генератор псевдослучайных чисел ) для последовательностей равномерно распределенных псевдослучайных чисел, введенный в 1989 году и остается в силе в 2019 году, через тридцать лет.

Представленный RSWikramaratna [1] ACORN изначально был разработан для использования в геостатистическом и геофизическом моделировании Монте-Карло , а затем был расширен для использования на параллельных компьютерах . [2]

В последующие десятилетия теоретический анализ (формальное доказательство сходимости и статистические результаты), эмпирическое тестирование (с использованием стандартных наборов тестов) и практическая работа по применению продолжались, несмотря на появление и продвижение других более известных [но не обязательно более эффективных] ГПСЧ.

Преимущества [ править ]

Основными преимуществами ACORN являются простота концепции и кода, скорость выполнения, большая длина периода и математически подтвержденная сходимость. [3]

Алгоритм может быть расширен, если будущие приложения потребуют псевдослучайных чисел «лучшего качества» и более длительного периода, путем увеличения порядка и модуля по мере необходимости. Кроме того, недавнее исследование показало, что генераторы ACORN проходят все тесты в наборе тестов TestU01 , текущая версия 1.2.3, с соответствующим выбором параметров и с несколькими очень простыми ограничениями на выбор инициализации; Стоит отметить, как указали авторы TestU01, что некоторые широко используемые генераторы псевдослучайных чисел терпят неудачу в некоторых тестах.

ACORN особенно просто реализовать в точной целочисленной арифметике на различных компьютерных языках, используя всего несколько строк кода. [4] Целочисленная арифметика предпочтительнее реальной арифметики по модулю 1 в исходном представлении, так как в этом случае алгоритм является воспроизводимым, производя точно такую ​​же последовательность на любой машине и на любом языке, [2] и его периодичность математически доказуема.

Генератор ACORN не получил широкого распространения некоторых других PRNG, хотя он включен в подпрограммы библиотеки Fortran и C NAG Numerical Library . [5] Для этого выдвигались разные причины. [6] Тем не менее, теоретические и эмпирические исследования продолжаются, чтобы еще больше оправдать продолжающееся использование ACORN в качестве надежного и эффективного PRNG.

Provisos [ править ]

При тестировании ACORN показывает очень хорошие результаты при соответствующих параметрах. [6] Однако в нынешнем виде ACORN не подходит для криптографии . [ необходима цитата ]

В отношении ACORN было мало критических оценок. Один из них, [7] предупреждает о неудовлетворительной конфигурации процедуры acorni () при использовании GSLIB GeoStatistical моделирования и библиотеки моделирования, [8] и предлагает простое решение этой проблемы. По сути, параметр модуля должен быть увеличен, чтобы избежать этой проблемы. [9] [6]

Другая краткая ссылка на ACORN просто заявляет, что «... генератор ACORN, предложенный недавно […], фактически эквивалентен MLCG с матрицей A такой, что a ~ = 1 для i 2 j, aq = 0 в противном случае» [10], но анализ не продвигается.

ACORN - это не то же самое, что ACG (аддитивный конгруэнтный генератор), и не следует путать с ним - ACG, похоже, использовался для варианта LCG ( линейного конгруэнтного генератора ), описанного Кнутом (1997).

История и развитие [ править ]

Первоначально ACORN был реализован в реальной арифметике в FORTRAN77, [1] и показал лучшую скорость выполнения и статистическую производительность, чем линейные конгруэнтные генераторы и генераторы Чебышева.

В 1992 году были опубликованы дальнейшие результаты [11], в которых реализован генератор псевдослучайных чисел ACORN в точной целочисленной арифметике, который обеспечивает воспроизводимость на разных платформах и языках, и утверждается, что для произвольной арифметики с реальной точностью можно доказать сходимость ACORN. последовательность к k-распределению по мере увеличения точности.

В 2000 году ACORN был заявлен как частный случай множественного рекурсивного генератора (и, следовательно, матричного генератора) [2], и это было формально продемонстрировано в 2008 году [12] в статье, в которой также были опубликованы результаты эмпирического исследования Дихарда. тесты и сравнения с NAG LCG ( Linear Congruential Generator ).

В 2009 г. было дано формальное доказательство [4] теоретической сходимости ACORN к k-распределению для модуля M = 2 м, когда m стремится к бесконечности (как ранее упоминалось в 1992 г. [11] ), вместе с подтверждающими это эмпирическими результатами, которые показали, что генераторы ACORN могут пройти все тесты в стандартном наборе TESTU01 [13] для тестирования PRNG (при выборе соответствующих параметров порядка и модуля).

С 2009 года ACORN был включен в подпрограммы FORTRAN и библиотеки C NAG ( Numerical Algorithms Group ) [14] [5] вместе с другими хорошо известными подпрограммами PRNG. Эта реализация ACORN работает для произвольно большого модуля и порядка и доступна для загрузки исследователям. [5]

ACORN также был реализован в библиотеке геостатистического моделирования GSLIB. [8]

Совсем недавно ACORN был представлен в апреле 2019 года на стендовой конференции на конференции по численным алгоритмам для высокопроизводительной вычислительной науки [15] в Королевском обществе в Лондоне, а в июне 2019 года на семинаре группы численного анализа в математическом институте. Институт Оксфордского университета . [16], где было заявлено, что статистические характеристики лучше, чем у некоторых очень широко используемых генераторов (включая Mersenne Twister MT19937) и сопоставимы с лучшими доступными в настоящее время методами »и что генераторы ACORN надежно проходят все тесты в TestU01, в то время как некоторые другие генераторы, включая Mersenne Twister, не проходят все эти тесты. Плакат и презентацию можно найти по адресу . [9]

Пример кода [ править ]

Следующий пример на Fortran77 был опубликован в 2008 году [12], который включает обсуждение того, как инициализировать:

  ФУНКЦИЯ ДВОЙНОЙ ТОЧНОСТИ ACORNJ ( XDUMMY ) C C Реализация на Фортране генератора случайных чисел ACORN C порядка меньше или равного 120 (более высокие порядки могут быть получены путем увеличения значения параметра MAXORD) и модуля C меньше или равного 2 ^ 60 . C C После соответствующей инициализации общего блока / IACO2 / C каждый вызов ACORNJ генерирует одну переменную, взятую из C с равномерным распределением в единичном интервале. C ЯВНАЯ ДВОЙНАЯ ТОЧНОСТЬ ( A - H , O - Z   ) ПАРАМЕТР ( MAXORD = 120 , MAXOP1 = MAXORD + 1 ) ОБЩИЙ / IACO2 / KORDEJ , MAXJNT , IXV1 ( MAXOP1 ), IXV2 ( MAXOP1 ) DO 7 I = 1 , KORDEJ IXV1 ( I + 1 ) = ( IXV1 ( I + 1 ) + IXV1 ( I ))              IXV2 ( I + 1 ) = ( IXV2 ( I + 1 ) + IXV2 ( I )) IF ( IXV2 ( I + 1 ). GE . MAXJNT ) ТО IXV2 ( I + 1 ) = IXV2 ( I + 1 ) - MAXJNT IXV1 ( I + 1 ) = IXV1 ( I +        1 ) + 1 ENDIF IF ( IXV1 ( I + 1 ). GE . MAXJNT ) IXV1 ( I + 1 ) = IXV1 ( I + 1 ) - MAXJNT  7 CONTINUE ACORNJ = ( DBLE ( IXV1 ( KORDEJ + 1 )) 1 + DBLE ( IXV2 ( KORDEJ + 1 )) /            MAXJNT ) / MAXJNT RETURN END

Внешние ссылки [ править ]

Веб-сайт ACORN [1] (ACORN.wikramaratna.org) содержит информацию о концепции и алгоритме ACORN, его авторе, полный список ссылок и информацию о текущих направлениях исследований.

Ссылки [ править ]

  1. ^ а б Wikramaratna, RS (1989). ACORN - новый метод генерации последовательностей равномерно распределенных псевдослучайных чисел. Журнал вычислительной физики. 83. 16-31.
  2. ^ а б в Р.С. Викрамаратна, Генерация псевдослучайных чисел для параллельной обработки - подход разделения, SIAM News 33 (9) (2000).
  3. ^ «ЖЕЛУДОЙ понятие и алгоритм» . acorn.wikramaratna.org/concept.html .
  4. ^ а б Р.С. Викрамаратна, Теоретические и эмпирические результаты сходимости для генераторов аддитивных конгруэнтных случайных чисел, Журнал вычислительной и прикладной математики (2009), DOI: 10.1016 / j.cam.2009.10.015
  5. ^ a b c "g05 Введение в главу: библиотека NAG, Марка 26" . www.nag.co.uk .
  6. ^ a b c "Инициализация желудя и критика" . acorn.wikramaratna.org/critique.html .
  7. ^ Ортис, Хулиан и В. Дойч, Клейтон. (2014). Генерация случайных чисел с помощью acorni: предупреждение.
  8. ^ a b GsLib Пакет с открытым исходным кодом, посвященный геостатистике, исходный код на Fortran 77 и 90.
  9. ^ a b «Желудевые ссылки и ссылки» . acorn.wikramaratna.org/references.html .
  10. ^ L'Ecuyer, Пьер. (1990). Случайные числа для моделирования .. Commun. ACM. 33. 85-97. 10.1145 / 84537.84555.
  11. ^ а б Р.С. Викрамаратна, Теоретические основы генератора случайных чисел ACORN, Отчет AEA-APS-0244, AEA Technology, Winfrith, Dorset, UK, 1992.
  12. ^ a b Викрамаратна, Рой (2008). «Аддитивный конгруэнтный генератор случайных чисел - частный случай многократно рекурсивного генератора» . J. Comput. Прил. Математика . 216 : 371–387. DOI : 10.1016 / j.cam.2007.05.018 .
  13. ^ P. L'Ecuyer, R. Simard, TestU01: AC-библиотека для эмпирического тестирования генераторов случайных чисел, ACM Trans. по математике. Программное обеспечение 33 (4) (2007) Статья 22.
  14. ^ NAG, Numerical Algorithms Group (NAG) Библиотека Fortran Mark 22, Numerical Algorithms Group Ltd., Оксфорд, Великобритания, 2009.
  15. ^ «Численные алгоритмы для высокопроизводительных вычислений» . Королевское общество .
  16. ^ «Генератор аддитивных конгруэнтных случайных чисел (ACORN) - псевдослучайные последовательности, которые хорошо распределены в k-измерениях» . Математический институт Оксфордского университета .