ACORN（乱数ジェネレーター）

ACORNまたは「加法混合乱数」ジェネレーターは、均一に分布した疑似乱数シーケンス用の堅牢な疑似乱数ジェネレーター (PRNG) ファミリであり、1989年に導入され、30 年後の 2019 年でもまだ有効です。

RSWikramaratnaによって導入された[ 1 ] ACORNは、もともと地統計学および地球物理学のモンテカルロシミュレーションで使用するために設計され、後に並列コンピュータで使用できるように拡張されました。[ 2 ]

その後の数十年にわたり、他のよく知られた（ただし必ずしもパフォーマンスが優れているわけではない）PRNG の登場と推進にもかかわらず、理論的分析（収束の正式な証明と統計的結果）、経験的テスト（標準テスト スイートを使用）、および実際のアプリケーション作業が継続して行われてきました。

利点

ACORNの主な利点は、概念とコーディングの単純さ、実行速度、長い周期、そして数学的に証明された収束性です。[ 3 ]

将来のアプリケーションで「より高品質な」疑似乱数とより長い周期が求められる場合、必要に応じて次数と係数を増やすことで、このアルゴリズムを拡張できます。さらに、最近の研究では、ACORNジェネレーターは、適切なパラメータ選択と初期化の選択に関するいくつかの非常に単純な制約により、 TestU01テストスイート（現在のバージョン1.2.3）のすべてのテストに合格することが示されています。TestU01の著者が指摘しているように、広く使用されている疑似乱数ジェネレーターの中には、一部のテストで重大な不合格を示すものもあることは注目に値します。

ACORNは、様々なコンピュータ言語で、わずか数行のコードを使用して、正確な整数演算で実装するのが特に簡単です。 [ 4 ] 整数演算は、元のプレゼンテーションの1を法とする実数演算よりも優先されます。そのアルゴリズムは再現可能であり、どのマシンでもどの言語でもまったく同じシーケンスを生成するためです。[ 2 ]また、その周期性は数学的に証明可能です。

ACORNジェネレータは、 NAG Numerical LibraryのFortranおよびCライブラリルーチンに含まれているにもかかわらず、他のPRNGに広く採用されていません。[ 5 ]これにはさまざまな理由が挙げられています。[ 6 ]ただし、ACORNを堅牢で効果的なPRNGとして継続的に使用することを正当化するための理論的および実証的な研究が進行中です。

ただし書き

テストでは、ACORNは適切なパラメータで非常に優れたパフォーマンスを発揮します。[ 6 ]しかし、現状ではACORNは暗号化に適しているとは示されていません

ACORNに関する批判的な評価は少ない。そのうちの一つ[ 7 ]は、 GSLIB GeoStatisticalモデリングおよびシミュレーションライブラリを使用する際にacorni()ルーチンの設定が不十分であると警告し[ 8 ]、この問題に対する簡単な解決策を提案している。基本的に、この問題を回避するには、係数パラメータを増やす必要がある。[ 9 ] [ 6 ]

ACORNに関する別の簡単な言及では、「最近提案されたACORNジェネレータは、実際には、i 2 jに対してa~ = 1、それ以外の場合はaq = 0となるような行列Aを持つMLCGと同等である」とだけ述べられているが[ 10 ]、それ以上の分析は行われていない。

ACORN は ACG (Additive Congruential Generator) と同じではないので混同しないでください。ACG は、Knuth (1997) によって説明された LCG ( Linear Congruential Generator ) のバリエーションとして使用されているようです。

歴史と発展

当初、ACORNはFORTRAN77の実数演算で実装され、[ 1 ]線形合同法生成器やチェビシェフ法生成器よりも優れた実行速度と統計性能を示すことが示されました

1992年にはさらなる成果が発表され、[ 11 ] ACORN疑似乱数生成器を正確な整数演算で実装することで、異なるプラットフォームや言語間での再現性を確保し、任意の実数精度演算では精度が上がるにつれてACORNシーケンスがk分布に収束することを証明できると述べています。

2000年にACORNは多重再帰生成器（したがって行列生成器）の特殊なケースであると述べられ、[ 2 ]、これは2008年に[ 12 ]論文で正式に実証され、その論文では経験的ダイハードテストの結果とNAG LCG（線形合同生成器）との比較も発表されました。

2009年には、 ACORNが係数M= 2mに対してk分布に理論的に収束することが正式に証明され[ 4 ]、mが無限大に近づくにつれて（1992年にすでに示唆されていたように[ 11 ] ）、これを裏付ける実験結果とともに、ACORNジェネレータはPRNGのテストのための標準的なTESTU01 [ 13 ]スイートのすべてのテストに合格できることが示されました（適切な順序と係数パラメータが選択されている場合）。

2009年以降、ACORNはNAG（Numerical Algorithms Group）のFORTRANおよびCライブラリルーチン[ 14 ] [ 5 ]に、他のよく知られたPRNGルーチンと共に組み込まれています。このACORNの実装は、任意の大きな係数と次数で動作し、研究者がダウンロードできます。[ 5 ]

ACORNはGSLIB地理統計モデリングおよびシミュレーションライブラリにも実装されています。[ 8 ]

最近では、ACORNは2019年4月にロンドン王立協会で開催された高性能計算科学のための数値アルゴリズムに関する会議のポスターセッションで発表されました[ 15 ] 、および2019年6月にオックスフォード大学数学研究所の数値解析グループのセミナーで発表されました。[ 16 ]そこでは、統計的パフォーマンスが非常に広く使用されているいくつかのジェネレータ（メルセンヌツイスターMT19937を含む）よりも優れており、現在利用可能な最良の方法に匹敵すると述べられており、ACORNジェネレータはTestU01のすべてのテストに確実に合格することが示されているのに対し、メルセンヌツイスターを含む他のジェネレータはこれらのテストをすべて合格していないことが示されています。ポスターとプレゼンテーションは次の場所でご覧いただけます。[ 9 ]

コード例

次のFortran77の例は2008年に公開されました[ 12 ]。 初期化方法についての説明が含まれています 

倍精度関数ACORNJ ( XDUMMY ) C C次数が 120 以下 (パラメーター値 MAXORD を増やすと、より高い次数を取得できます)、係数が 2^60 以下であるACORN 乱数ジェネレーター C の Fortran 実装。 C C 共通ブロック /IACO2/ C を適切に初期化した後、ACORNJ を呼び出すたびに、単位間隔にわたる均一分布から抽出された単一の変数が生成されます。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 ) 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継続ACORNJ = ( DBLE ( IXV1 ( KORDEJ + 1 )) 1 + DBLE ( IXV2 ( KORDEJ + 1 )) / MAXJNT ) / MAXJNT RETURN END

参考文献

  1. ^ a b Wikramaratna, RS (1989). ACORN — 一様分布の疑似乱数列を生成する新しい手法. Journal of Computational Physics. 83. 16-31
  2. ^ a b c R.S. Wikramaratna、「並列処理のための疑似乱数生成 - 分割アプローチ」、SIAM News 33 (9) (2000)。
  3. ^ 「ACORNの概念とアルゴリズム」acorn.wikramaratna.org/concept.html .
  4. ^ a b R.S. Wikramaratna, 加法合同型乱数生成器の理論的および経験的収束結果, Journal of Computational and Applied Mathematics (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 の初期化と批評」 . acorn.wikramaratna.org/critique.html。
  7. ^オルティス、フリアン、V. ドイチュ、クレイトン。 （2014年）。 acorni による乱数生成: 警告。
  8. ^ a b GsLib地理統計学専用のオープンソース パッケージ。ソース コードは Fortran 77 および 90 で書かれています。
  9. ^ a b「ACORN の参考資料とリンク」。acorn.wikramaratna.org / references.html 。
  10. ^レキュイエ、ピエール。 （1990年）。シミュレーション用の乱数。共通。 ACM。 33. 85-97。 10.1145/84537.84555。
  11. ^ a b R.S. Wikramaratna、「ACORN乱数ジェネレータの理論的背景」、レポートAEA-APS-0244、AEA Technology、ウィンフリス、ドーセット、英国、1992年。
  12. ^ a b Wikramaratna, Roy (2008). 「加法合同型乱数生成器 ― 多重再帰生成器の特殊なケース」 . J. Comput. Appl. Math . 216 (2): 371– 387. Bibcode : 2008JCoAM.216..371W . doi : 10.1016/j.cam.2007.05.018 .
  13. ^ P. L'Ecuyer, R. Simard, TestU01: 乱数ジェネレータの経験的テストのためのACライブラリ、ACM Trans. on Math. Software 33 (4) (2007) 記事22。
  14. ^ NAG、Numerical Algorithms Group (NAG) Fortran ライブラリ Mark 22、Numerical Algorithms Group Ltd.、オックスフォード、英国、2009 年。
  15. ^ 「高性能計算科学のための数値アルゴリズム」王立協会。
  16. ^ 「加法合同型乱数（ACORN）ジェネレーター - k次元に適切に分布する疑似乱数シーケンス」オックスフォード大学数学研究所。
「 https://en.wikipedia.org/w/index.php?title=ACORN_(random_number_generator)&oldid=1316680002」より取得