ЖЕЛУДЬ (генератор случайных чисел)

Генераторы ACORN « или Аддитивные » представляют собой конгруэнтные числа случайные . ( надежное семейство генераторов псевдослучайных чисел PRNG) для последовательностей равномерно распределенных псевдослучайных чисел, представленное в 1989 году и все еще актуальное в 2019 году, тридцать лет спустя

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

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

Преимущества

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

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

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

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

Условия

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

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

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

ЖЕЛУДЬ — это не то же самое, что ACG (аддитивный конгруэнтный генератор), и его не следует путать с ним — ACG, по-видимому, использовался для варианта LCG ( линейный конгруэнтный генератор ), описанного Кнутом (1997).

История и развитие

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

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

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

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

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

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

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

Пример кода

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

      DOUBLE PRECISION FUNCTION ACORNJ(XDUMMY)
C
C          Fortran implementation of ACORN random number generator
C          of order less than or equal to 120 (higher orders can be
C          obtained by increasing the parameter value MAXORD) and
C          modulus less than or equal to 2^60.
C
C          After appropriate initialization of the common block /IACO2/
C          each call to ACORNJ generates a single variate drawn from
C          a uniform distribution over the unit interval.
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
      PARAMETER (MAXORD=120,MAXOP1=MAXORD+1)
      COMMON /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) THEN
          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 (ACORN.wikramaratna.org) : содержит информацию о концепции и алгоритме ACORN, ее авторе, полный список литературы, а также информацию о текущих направлениях исследований.

Ссылки

^ Jump up to: ^а ^б Викрамаратна, Р.С. (1989). ЖЕЛУДЬ — новый метод генерации последовательностей равномерно распределенных псевдослучайных чисел. Журнал вычислительной физики. 83. 16-31.
^ Jump up to: ^а ^б ^с Р. С. Викрамаратна, Генерация псевдослучайных чисел для параллельной обработки — подход разделения, SIAM News 33 (9) (2000).
^ «Концепция и алгоритм ЖЕЛУДЯ» . acorn.wikramaratna.org/concept.html .
^ Jump up to: ^а ^б Р. С. Викрамаратна, Теоретические и эмпирические результаты сходимости аддитивных конгруэнтных генераторов случайных чисел, Журнал вычислительной и прикладной математики (2009), два : 10.1016/j.cam.2009.10.015
^ Jump up to: ^а ^б ^с «g05 Введение в главу: Библиотека NAG, Марк 26» . www.nag.co.uk.
^ Jump up to: ^а ^б ^с «Инициализация и критика ACORN» . acorn.wikramaratna.org/critique.html .
^ Ортис, Джулиан и В. Дойч, Клейтон. (2014). Генерация случайных чисел с помощью желудей: предупреждение.
^ Jump up to: ^а ^б GsLib Пакет с открытым исходным кодом, посвященный геостатистике, исходный код на Фортране 77 и 90.
^ Jump up to: ^а ^б «Ссылки и ссылки ЖЕЛУДЯ» . acorn.wikramaratna.org/references.html .
^ Л'Экуйер, Пьер. (1990). Случайные числа для моделирования.. Обычное. АКМ. 33. 85-97. 10.1145/84537.84555.
^ Jump up to: ^а ^б Р. С. Викрамаратна, Теоретические основы генератора случайных чисел ACORN, Отчет AEA-APS-0244, AEA Technology, Уинфрит, Дорсет, Великобритания, 1992.
^ Jump up to: ^а ^б Викрамаратна, Рой (2008). «Аддитивный конгруэнтный генератор случайных чисел – частный случай множественного рекурсивного генератора» . Дж. Компьютер. Прил. Математика . 216 (2): 371–387. Бибкод : 2008JCoAM.216..371W . дои : 10.1016/j.cam.2007.05.018 .
^ П. Л'Экуйер, Р. Симард, TestU01: библиотека AC для эмпирического тестирования генераторов случайных чисел, ACM Trans. по математике. Программное обеспечение 33 (4) (2007 г.) Статья 22.
^ NAG, Группа числовых алгоритмов (NAG), Библиотека Фортрана Mark 22, Numerical Algorithms Group Ltd., Оксфорд, Великобритания, 2009.
^ «Численные алгоритмы для высокопроизводительных вычислений» . Королевское общество .
^ «Генератор аддитивных конгруэнтных случайных чисел (ACORN) — псевдослучайные последовательности, хорошо распределенные в k-измерениях» . Математический институт Оксфордского университета .

[:3-1] Jump up to: ^а ^б Викрамаратна, Р.С. (1989). ЖЕЛУДЬ — новый метод генерации последовательностей равномерно распределенных псевдослучайных чисел. Журнал вычислительной физики. 83. 16-31.

[:6-2] Jump up to: ^а ^б ^с Р. С. Викрамаратна, Генерация псевдослучайных чисел для параллельной обработки — подход разделения, SIAM News 33 (9) (2000).

[wwwConcept-3] «Концепция и алгоритм ЖЕЛУДЯ» . acorn.wikramaratna.org/concept.html .

[:1-4] Jump up to: ^а ^б Р. С. Викрамаратна, Теоретические и эмпирические результаты сходимости аддитивных конгруэнтных генераторов случайных чисел, Журнал вычислительной и прикладной математики (2009), два : 10.1016/j.cam.2009.10.015

[:4-5] Jump up to: ^а ^б ^с «g05 Введение в главу: Библиотека NAG, Марк 26» . www.nag.co.uk.

[wwwCritique-6] Jump up to: ^а ^б ^с «Инициализация и критика ACORN» . acorn.wikramaratna.org/critique.html .

[7] Ортис, Джулиан и В. Дойч, Клейтон. (2014). Генерация случайных чисел с помощью желудей: предупреждение.

[GsLib-8] Jump up to: ^а ^б GsLib Пакет с открытым исходным кодом, посвященный геостатистике, исходный код на Фортране 77 и 90.

[wwwReferences-9] Jump up to: ^а ^б «Ссылки и ссылки ЖЕЛУДЯ» . acorn.wikramaratna.org/references.html .

[10] Л'Экуйер, Пьер. (1990). Случайные числа для моделирования.. Обычное. АКМ. 33. 85-97. 10.1145/84537.84555.

[:2-11] Jump up to: ^а ^б Р. С. Викрамаратна, Теоретические основы генератора случайных чисел ACORN, Отчет AEA-APS-0244, AEA Technology, Уинфрит, Дорсет, Великобритания, 1992.

[:0-12] Jump up to: ^а ^б Викрамаратна, Рой (2008). «Аддитивный конгруэнтный генератор случайных чисел – частный случай множественного рекурсивного генератора» . Дж. Компьютер. Прил. Математика . 216 (2): 371–387. Бибкод : 2008JCoAM.216..371W . дои : 10.1016/j.cam.2007.05.018 .

[13] П. Л'Экуйер, Р. Симард, TestU01: библиотека AC для эмпирического тестирования генераторов случайных чисел, ACM Trans. по математике. Программное обеспечение 33 (4) (2007 г.) Статья 22.

[14] NAG, Группа числовых алгоритмов (NAG), Библиотека Фортрана Mark 22, Numerical Algorithms Group Ltd., Оксфорд, Великобритания, 2009.

[15] «Численные алгоритмы для высокопроизводительных вычислений» . Королевское общество .

[16] «Генератор аддитивных конгруэнтных случайных чисел (ACORN) — псевдослучайные последовательности, хорошо распределенные в k-измерениях» . Математический институт Оксфордского университета .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]