スペクトルテスト
線形合同生成器の統計的検定
RANDUで生成された10万個の値の3次元プロット。各点は連続する3つの疑似乱数を表します。点が15個の2次元 平面に分布していることが明確にわかります。

スペクトルテストは、擬似乱数生成器（PRNG）の一種である線形合同型生成器（LCG）の品質を統計的に検定するものです。[1] LCGは、2次元以上にプロットすると直線または超平面が形成され、その上にすべての可能な出力を見つけることができるという特性があります。[2]スペクトルテストは、これらの平面間の距離を比較します。平面が離れているほど、生成器の品質は低下します。[3]このテストはLCGの格子構造を調べるために考案されているため、他のPRNGファミリーには適用できません。

ドナルド・クヌース[4]によれば、これはこれまで知られている中で最も強力な検定法である。なぜなら、ほとんどの統計検定に合格するLCGを不合格にすることができるからである。IBMのサブルーチンRANDU [5] [6] LCGは、3次元以上ではこの検定に不合格となる。

PRNGがシーケンス を生成するとします。シーケンス を覆う平行面間の最大距離を とします。スペクトルテストは、シーケンスが急速に減衰しないことを確認します。 あなた 1 、 あなた 2 、 … {\displaystyle u_{1},u_{2},\dots } 1 / ν t {\displaystyle 1/\nu_{t}} { （ あなた n + 1 : n + t ） ∣ n ＝ 0 、 1 、 … } {\displaystyle \{(u_{n+1:n+t})\mid n=0,1,\dots \}} ν 2 、 ν 3 、 ν 4 、 … {\displaystyle \nu _{2},\nu _{3},\nu _{4},\dots }

Knuth は、次の 5 つの数値がそれぞれ 0.01 より大きいことを確認することを推奨しています。 ここで、 は LCG の係数です。 μ 2 ＝ π ν 2 2 / メートル 、 μ 3 ＝ 4 3 π ν 3 3 / メートル 、 μ 4 ＝ 1 2 π 2 ν 4 4 / メートル 、 μ 5 ＝ 8 15 π 2 ν 5 5 / メートル 、 μ 6 ＝ 1 6 π 3 ν 6 6 / メートル 、 {\displaystyle {\begin{aligned}\mu _{2}&=\pi \nu _{2}^{2}/m,&\mu _{3}&={\frac {4}{3}}\pi \nu _{3}^{3}/m,&\mu _{4}&={\frac {1}{2}}\pi ^{2}\nu _{4}^{4}/m,\\[1ex]&&\mu _{5}&={\frac {8}{15}}\pi ^{2}\nu _{5}^{5}/m,&\mu _{6}&={\frac {1}{6}}\pi ^{3}\nu _{6}^{6}/m,\end{aligned}}} メートル {\displaystyle m}

功績の数字

クヌースは、分離が理論上の最小値にどれだけ近いかを表す 性能指数を定義している。スティールとヴィグナの再記法によれば、次元 に対して、この数値は[7] : 3 と定義される。 ここで は前述のように定義され、 は次元dのエルミート定数である。は、可能な限り最小の面間分離である。[7] : 3  1 / ν t {\displaystyle 1/\nu_{t}} d {\displaystyle d} f d {\displaystyle f_{d}} f d （ メートル 、 1つの ） ＝ ν d / （ γ d 1 / 2 メートル d ） 、 {\displaystyle f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),} 1つの 、 メートル 、 ν d {\displaystyle a,m,\nu _{d}} γ d {\displaystyle \gamma_{d}} γ d 1 / 2 メートル d {\displaystyle \gamma _{d}^{1/2}{\sqrt[{d}]{m}}}

L'Ecuyer 1991はさらに、いくつかの次元にわたる の最小値に対応する2つの尺度を導入しています。 [8]再び表記を変えると、は次元2から までのLCGの最小値であり、乗法合同型擬似乱数生成器（MCG）、つまり乗算のみが使用されるもの、つまり と同じです。SteeleとVignaは、 の計算方法がこれら2つのケースで異なるため、別々の値が必要になることを指摘しています。[7] : 13 彼らはさらに、「調和」加重平均性能指数（および）を定義しています。[7] : 13  f d {\displaystyle f_{d}} M d + （ メートル 、 1つの ） {\displaystyle {\mathcal {M}}_{d}^{+}(m,a)} f d {\displaystyle f_{d}} d {\displaystyle d} M d ∗ （ メートル 、 1つの ） {\displaystyle {\mathcal {M}}_{d}^{*}(m,a)} c ＝ 0 {\displaystyle c=0} f d {\displaystyle f_{d}} H d + （ メートル 、 1つの ） {\displaystyle {\mathcal {H}}_{d}^{+}(m,a)} H d ∗ （ メートル 、 1つの ） {\displaystyle {\mathcal {H}}_{d}^{*}(m,a)}

例

悪名高いRANDUの小さな変種には次の特徴がある: [4] : (表1)  × n + 1 ＝ 65539 × n モッド 2 29 {\displaystyle x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}}

d 2 3 4 5 6 7 8
ν2
日 		536936458 118 116 116 116
μ d 3.14 10 −5 10 −4 10 −3 0.02
f d [a] 0.520224 0.018902 0.084143 0.207185 0.368841 0.552205 0.578329

総合的な評価は次の通りです: 、。[a] M 8 ∗ （ 65539 、 2 29 ） ＝ 0.018902 {\displaystyle {\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902} H 8 ∗ （ 65539 、 2 29 ） ＝ 0.330886 {\displaystyle {\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886}

ジョージ・マルサリア（1972）は、覚えやすく、特に大きなスペクトルテスト番号を持っているため、「すべての乗数の中で最良の候補」であると考えています。[9] × n + 1 ＝ 69069 × n モッド 2 32 {\displaystyle x_{n+1}=69069\,x_{n}{\bmod {2}}^{32}}

d 2 3 4 5 6 7 8
ν2
日 		4243209856 2072544 52804 6990 242
μ d [b] 3.10 2.91 3.20 5.01 0.017
f d [a] 0.462490 0.313127 0.457183 0.552916 0.376706 0.496687 0.685247

総合的な評価は次の通りです: 、。[a] M 8 ∗ （ 69069 、 2 32 ） ＝ 0.313127 {\displaystyle {\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127} H 8 ∗ （ 69069 、 2 32 ） ＝ 0.449578 {\displaystyle {\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578}

Steele & Vigna (2020)は、 m = 2 nとaのビット長の様々な選択肢に対して、最も高い総合的な性能指数を持つ乗算器を提供している。また、個々の値と、それらの値を計算するためのソフトウェアパッケージも提供している。[7] : 14–5 例えば、彼らはm = 2 32の場合の最良の17ビットaは次の式であると報告している。 f d {\displaystyle f_{d}}

  • LCG（c≠0）の場合、0x1dab5（121525）。, . [7] : 14  M 8 + ＝ 0.6403 {\displaystyle {\mathcal {M}}_{8}^{+}=0.6403} H 8 + ＝ 0.6588 {\displaystyle {\mathcal {H}}_{8}^{+}=0.6588}
  • MCG（c = 0）の場合、0x1e92d（125229）。, . [7] : 14  M 8 ∗ ＝ 0.6623 {\displaystyle {\mathcal {M}}_{8}^{*}=0.6623} H 8 ∗ ＝ 0.7497 {\displaystyle {\mathcal {H}}_{8}^{*}=0.7497}

追加の図解

両方の関係がカイ二乗検定に合格しているという事実にもかかわらず、最初の LCG は、生成する順序によって生成できる値の範囲が均等に分散されていないため、2 番目の LCG よりもランダム性が低くなります。

参考文献

  1. ^ abcd Steele & Vigna (2020)のソフトウェア、プログラム「mspect」(src/spect.cpp、乗法モード)を使用して計算しました。
  2. ^ νから計算2
    日    Marsaglia が報告した。
  1. ^ Williams, KB; Dwyer, Jerry (1996年8月1日)、「Testing Random Number Generators, Part 2」、Dr. Dobb's Journal 、 2012年1月26日閲覧。。
  2. ^ Marsaglia, George (1968年9月). 「乱数は主に平面に落ちる」(PDF) . PNAS . 61 (1): 25– 28. Bibcode :1968PNAS...61...25M. doi : 10.1073/pnas.61.1.25 . PMC 285899. PMID 16591687  . 
  3. ^ Jain, Raj. 「乱数生成器のテスト（講義）」（PDF） .セントルイス・ワシントン大学. 2016年12月2日閲覧。
  4. ^ ab Knuth, Donald E. (1981)、「3.3.4: スペクトルテスト」、The Art of Computer Programming volume 2: Seminumerical algorithms (第2版)、Addison-Wesley。
  5. ^ IBM、 System/360 Scientific Subroutine Package、バージョン II、プログラマーズ・マニュアル、H20-0205-1、1967 年、54 ページ。
  6. ^ International Business Machines Corporation (1968). 「IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III」(PDF) . Stan's Library . II . White Plains, NY: IBM Technical Publications Department: 77. doi :10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3.
  7. ^ abcdefg Steele, Guy L. Jr. ; Vigna, Sebastiano (2022年2月) [2020年1月15日]. 「合同型擬似乱数生成器のための計算容易かつスペクトル的に良好な乗算器」.ソフトウェア：実践と経験. 52 (2): 443– 458. arXiv : 2001.05304 . doi : 10.1002/spe.3030 .関連ソフトウェアとデータは https://github.com/vigna/CPRNG にあります。
  8. ^ L'Ecuyer, Pierre (1999年1月). 「異なるサイズと良好な格子構造を持つ線形合同型生成器の表」(PDF) .計算数学. 68 (225): 249– 260. Bibcode :1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024 . doi :10.1090/S0025-5718-99-00996-5.  必ず正誤表も読んでください。
  9. ^ Marsaglia, GEORGE (1972-01-01), Zaremba, SK (ed.), "The Structure of Linear Congruential Sequences", Applications of Number Theory to Numerical Analysis , Academic Press, pp.  249– 285, ISBN 978-0-12-775950-0、 2024年1月29日取得

さらに読む

  • エンタッチャー, カール (1998年1月). 「よく知られた線形合同型擬似乱数生成器の不良部分列」. ACM Transactions on Modeling and Computer Simulation . 8 (1): 61– 70. doi :10.1145/272991.273009.–多くのよく知られたLCGを （このテキストではこのように表記）リストします f d {\displaystyle f_{d}} S s {\displaystyle S_{s}}
    • この作品の拡張版は、Entacher, Karl (2001). 「線形構造を持つ選択された擬似乱数生成器のコレクション - 拡張版」として入手可能です。
「https://en.wikipedia.org/w/index.php?title=Spectral_test&oldid=1296114636」から取得