スペクトルテスト

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

ドナルド・クヌース^[4]によれば、これはこれまで知られているテストの中で最も強力なテストであり、ほとんどの統計テストに合格するLCGを失敗させることができる。IBMサブルーチンRANDU ^{[5] [6]} LCGは3次元以上ではこのテストに失敗する。

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

Knuth は、次の 5 つの数値がそれぞれ 0.01 より大きいことを確認することを推奨しています。 ここで、はLCG の係数です。 $${\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}${\displaystyle 1/\nu_{t}}$${\displaystyle d}$${\displaystyle f_{d}}$ $${\displaystyle f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),}$$${\displaystyle a,m,\nu _{d}}$${\displaystyle \gamma_{d}}$${\displaystyle \gamma _{d}^{1/2}{\sqrt[{d}]{m}}}$

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

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

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

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

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

Steele & Vigna (2020) は、 m = 2 ⁿのさまざまな選択肢と特定のビット長aに対して、最も総合的な性能指数の高い乗算器を提供しています。また、個々の値と、これらの値を計算するためのソフトウェアパッケージも提供しています。 ^{[7] : 14–5}たとえば、m = 2 ³²の場合の最良の 17 ビットa は次のようになると報告されています。 ${\displaystyle f_{d}}$

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

• Entacher , Karl (1998 年 1 月)。「よく知られている線形合同型擬似乱数生成器の不良部分列」。ACM Transactions on Modeling and Computer Simulation。8 ( 1): 61–70。doi :10.1145/272991.273009。–よく知られている多くのLCGを （このテキストではこのように表記）リストします${\displaystyle f_{d}}$${\displaystyle S_{s}}$
  • この作品の拡張版は、Entacher, Karl (2001)「線形構造を持つ選択された疑似乱数ジェネレーターのコレクション - 拡張バージョン」として入手できます。