線形合同生成器は、1948 年に DH Lehmer によって短縮形で導入され、乱数を生成するアルゴリズムが合同と線形関数に基づいた擬似乱数生成器です。
意味
乱数は、次の式に従って、各項が前の項に依存するシーケンスを形成します。
ここで、 a は乗数、 c は増分、 m はモジュールです。
最初の学期は、
mod演算 (a*X n +c を m でユークリッド除算した余り) のため、このシーケンスの項は 0 とm – 1 の間になります。さらに、各項は前の項に完全に依存するため、数値がが 2 回目に表示されると、シーケンス全体がこの番号から再現されます。ここで、数値が取り得る値の数は有限 ( mに等しい) であるため、シーケンスは一定時間後に繰り返されることになります。それは最終的には周期的であると言われています。
パラメータa 、 cおよびmの正しい選択
このタイプのアルゴリズムでは、ジェネレーターの品質は、 a 、 c 、およびmの選択に完全に依存します。これは、明確な理由もなく、X の選択に応じて多かれ少なかれランダムなシーケンスを生成するジェネレーターでは満足できないためです。 0 。
悪い例
a 、 c 、 m を「ランダムに」選択するのは良い考えではありません。例を見てみましょう。
線形合同生成器 ( a =25、 c =16、 m =256) を仮定すると、次のようになります。
- X 0 = 10の場合、シーケンス: 10, 10, 10, 10, 10, …
- 、 131、…
- 、 252、172、…
これらのシーケンスがランダムであるとは考えられないことは明らかです。
したがって、完全なランダム性に近い数値を取得したい場合は、ジェネレーターのパラメーターを慎重に選択する必要があることが明確にわかります。
次に、 a 、 c 、 m を適切に選択する方法を自問する必要があります。
モジュールの選択
合同ジェネレーターにはモジュロm の計算が含まれるため、アプリオリなユークリッド除算が必要になります。ジェネレーターを頻繁に使用すると、計算コストが大幅に増加する可能性があります。最も簡単な解決策は、 m = 2 e型のモジュールを使用することです。実際、コンピュータは自然に 2 進数で計算するため、そのような選択はコンピュータにとって完全に透過的であり、ユークリッド除算は不要になります。
ただし、このような選択には重要な制限があります。いわゆる下位ビット (右端のビット) は、上位部分 (左端のビット) よりもランダム性がはるかに低いです。実際、 d がmの約数である場合、シーケンスY n は次のようになります。
線形合同数列を満たす：
特に、 d = 2 kの場合、1 からeまでの固定kの場合、下位k桁の最大周期は 2 kで、明らかに m より小さいことがわかります。
この問題を解決するには、最上位ビットのみを保持する、つまり、取得した数値の左端のビットを切り捨てることができます。最後の k ビットを切り捨てると、0 から2 e − k − 1までの数値の擬似乱数生成器が得られます。
別の解決策は、次のタイプのモジュールを取得することで構成されます。
乗数と増分の選択
0 とm -1 の間の制約なしでシード X 0 を選択できるようにするには、ジェネレーターの周期を最大化するように努める必要があります。ここで、 aとcの値がわかっていることがわかり、これにより最大周期 ( mに等しい) を取得できるようになります。
線形合同生成器の周期は、次の場合にのみ最大になります。
- まずはmからです。 Gcd(c,m) = 1。
- m を割る素数p ごとに、(a-1) は p の倍数になります。
- (a-1) は、m が 1 の場合、4 の倍数です。
等価定理(if および if に限り) があることに注意してください。周期は、定理の性質を持つすべての値に対して最大であり、それらの値に対してのみ最大になります。
可能性
ポテンシャルは、特定のランダム性が不十分なジェネレーターを除外することを可能にする概念です。これは常に、最大周期を持つシーケンスに対してのみ定義されます (これは、上記の 2 番目の特性に従って)。他のジェネレーターでは常にポテンシャルを定義できるわけではなく、ポテンシャルが定義されていない優れたジェネレーターもあります。
最大周期を持つシーケンスの潜在的なs は、次のような最小の整数として定義されます。
最大周期のシーケンスについては、X 0 = 0 を取ることができるため、次のようになります。
したがって、 a n = ( (a-1) + 1 ) nの場合:
ポテンシャルが 3 以下の場合は、シーケンスが十分にランダムではないため、すぐに弱すぎるように見えます。実際には、5 以上のポテンシャルが推奨されます。
ただし、可能性という概念は、少数の悪いジェネレーターを除外するためにのみ存在することを覚えておいてください。電位が 5 を超える発電機は、いかなる場合でもすぐに良好であるとは見なされず、最初にいくつかのテストを受ける必要があります。
統計的検定
すべての擬似乱数発生器と同様に、線形合同発生器は承認される前に一連のテストを受ける必要があります。
これらの中で最もよく知られている周波数テストは、最大周期の線形合同発電機では通常問題になりませんが、他にも多くのテストがあります。シリーズテスト、ギャップテスト、ランテストなど
最も差別的なものの 1 つは、不良であることが証明された線形合同ジェネレーターが合格していないため、スペクトル テストです。
例
| アルゴリズム | もっている | c | メートル | 備考 |
|---|---|---|---|---|
| ランドゥ | 65539 | 0 | 2 31 | 偏見があり、強く推奨されません |
| ロバート・セジウィック発電機 | 31415821 | 1 | 10 8 | 興味深いですがお勧めしません（試してみてください） $$ {X_0 = 0~} $$ ) |
| 最低基準 | 16807 | 0 | 2 31 -1 |
- RANDU の定義
xn+1 = 65539 xn mod 2^31。
IBM System/370 に実装されているが、それを真剣に使用する必要がある人全員によって悪いと見なされている
- Turbo Pascal ジェネレーターは次のように定義されています。
xn+1 =(129 * xn + 907633385) mod 2^32
129 件中 1 件で xn+1 > xn であることがわかっており、これは科学的応用にとっては大きなバイアスとなります。さらに、129 は 2^n + 1 の形式であるため、生成される数値はそれほど「ランダム」ではありません [cf.クヌート p.23]。
- UNIXジェネレーター (幸いなことに、ANSI C 委員会は最上位 16 ビットのみを保持することを推奨しています):
xn+1 = (1103515245 * xn + 12345) mod 2^31。
Berkeley 4.2 のドキュメントでも、生成される数値の下位ビットが真のランダムではないことを認めています。
他の例
D. Knuth は、「Seminumerical Algorithms」の中で、一定数の高品質の線形合同生成器を列挙しています。最小標準を使用できない場合は、たとえば次のことを試すことができます。
xn+1 = (137 * xn + 187) mod 2^8
(256 個の数字の循環シーケンス、それでもチャンスはありますか?)
xn+1 = (1664525 * xn + 1013904223) mod 2^32
(クヌース＆ルイスジェネレータ)
xn+1 = 69069 * xn mod 2^32
(VAX で使用される、優れた被乗数を持つマルサグリア生成器)
xn+1 = (31167285 * xn + 1) mod 2^48
(ラヴォー&ジェンセンスジェネレータ)
xn+1 = (6,364,136,223,846,793,005 * xn + 1) mod 2^64
(ヘインズ発電機)
これらすべての場合において、変調器は 2 のべき乗であるため、生成される数値の最下位ビットはあまり「ランダム」ではありません。したがって、 Borland C++ ジェネレーターのように、最も重要なもの (たとえば 16 ビット) のみを保持することが望ましいです。
xn+1 = (22,695,477 * xn + 1) mod 2^32
そして xn+1 >> 16 を出力します。
その際、ジェネレーターの周期は同じままですが、シーケンス内でそれぞれが 65536 回発生する、0 から 65535 までの数値のみを生成します。