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に関する批判的な評価はほとんどありません。そのうちの1つ^[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]論文で正式に実証され、その論文では経験的なDiehardテストの結果とNAG LCG（線形合同ジェネレータ）との比較も発表されました。

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

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

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

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

コード例

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

      倍精度関数ACORNJ ( XDUMMY ) 
C C
次数が 120 以下 (パラメーター値 MAXORD を増やすと、より高い次数を取得できます)、係数が 2^60 以下であるACORN 乱数ジェネレーターの Fortran 実装。 
C C 共通ブロック /IACO2/ を適切に初期化した後、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

外部リンク

ACORN ウェブサイト (ACORN.wikramaratna.org) : ACORN の概念とアルゴリズム、その作成者、参考文献の完全なリスト、および現在の研究の方向性に関する情報が含まれています。

参考文献

^ ab Wikramaratna, RS (1989). ACORN — 均一に分布した疑似乱数列を生成する新しい方法。計算物理学ジャーナル。83. 16-31。
^ abc RS Wikramaratna、「並列処理のための疑似乱数生成 - 分割アプローチ」、SIAM News 33 (9) (2000)。
^ 「ACORN のコンセプトとアルゴリズム」。acorn.wikramaratna.org/concept.html。
^ ab RS Wikramaratna、加法合同型乱数生成器の理論的および経験的収束結果、Journal of Computational and Applied Mathematics (2009)、doi :10.1016/j.cam.2009.10.015
^ abc 「g05 章の紹介：NAG ライブラリ、マーク 26」。www.nag.co.uk。
^ abc 「ACORN の初期化と批評」. acorn.wikramaratna.org/critique.html。
^ オルティス、フリアン、V. ドイチュ、クレイトン。（2014年）。 acorni による乱数生成: 警告。
^ ab GsLib 地理統計学専用のオープンソースパッケージ。ソースコードは Fortran 77 および 90 で記述されています。
^ ab 「ACORN の参照とリンク」。acorn.wikramaratna.org/references.html。
^ レキュイエ、ピエール。（1990年）。シミュレーション用の乱数。共通。 ACM。 33. 85-97。 10.1145/84537.84555。
^ ab RS Wikramaratna、「ACORN 乱数ジェネレータの理論的背景」、レポート AEA-APS-0244、AEA Technology、ウィンフリス、ドーセット、英国、1992 年。
^ ab Wikramaratna, Roy (2008). 「加法合同型乱数生成器 - 多重再帰生成器の特殊なケース」J. Comput. Appl. Math . 216 (2): 371–387. Bibcode :2008JCoAM.216..371W. doi : 10.1016/j.cam.2007.05.018 .
^ P. L'Ecuyer、R. Simard、「TestU01: 乱数ジェネレーターの実証的テストのための AC ライブラリ」、ACM Trans. on Math. Software 33 (4) (2007) 記事 22。
^ NAG、Numerical Algorithms Group (NAG) Fortran ライブラリ Mark 22、Numerical Algorithms Group Ltd.、オックスフォード、英国、2009 年。
^ 「高性能計算科学のための数値アルゴリズム」。王立協会。
^ 「加法合同型乱数（ACORN）ジェネレーター - k次元に適切に分散された疑似ランダムシーケンス」オックスフォード大学数学研究所。

[:3-1] Wikramaratna, RS (1989). ACORN — 均一に分布した疑似乱数列を生成する新しい方法。計算物理学ジャーナル。83. 16-31。

[:6-2] RS Wikramaratna、「並列処理のための疑似乱数生成 - 分割アプローチ」、SIAM News 33 (9) (2000)。

[wwwConcept-3] 「ACORN のコンセプトとアルゴリズム」。acorn.wikramaratna.org/concept.html。

[:1-4] RS Wikramaratna、加法合同型乱数生成器の理論的および経験的収束結果、Journal of Computational and Applied Mathematics (2009)、doi :10.1016/j.cam.2009.10.015

[:4-5] 「g05 章の紹介：NAG ライブラリ、マーク 26」。www.nag.co.uk。

[wwwCritique-6] 「ACORN の初期化と批評」. acorn.wikramaratna.org/critique.html。

[7] オルティス、フリアン、V. ドイチュ、クレイトン。（2014年）。 acorni による乱数生成: 警告。

[GsLib-8] GsLib 地理統計学専用のオープンソースパッケージ。ソースコードは Fortran 77 および 90 で記述されています。

[wwwReferences-9] 「ACORN の参照とリンク」。acorn.wikramaratna.org/references.html。

[10] レキュイエ、ピエール。（1990年）。シミュレーション用の乱数。共通。 ACM。 33. 85-97。 10.1145/84537.84555。

[:2-11] RS Wikramaratna、「ACORN 乱数ジェネレータの理論的背景」、レポート AEA-APS-0244、AEA Technology、ウィンフリス、ドーセット、英国、1992 年。

[:0-12] 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次元に適切に分散された疑似ランダムシーケンス」オックスフォード大学数学研究所。