線形合同ジェネレータについて詳しく解説

導入

線形合同生成器は、1948 年に DH Lehmer によって短縮形で導入され、乱数を生成するアルゴリズムが合同と線形関数に基づいた擬似乱数生成器です。

意味

疑似乱数は、次の式に従って、各項が前の項に依存するシーケンスを形成します。

$$ {X_{n+1} = ( a \cdot X_n + c ) \mod m} $$

ここで、 a は乗数、 c は増分、 m はモジュールです。

最初の学期は、

はシードと呼ばれます。これにより、一見ランダムなシーケンスを生成することが可能になります。シードごとに、新しいシーケンスが作成されます。ただし、一部のシードは他のシードよりもランダムなシーケンスになる可能性があります。

mod演算 (a*X _n +c を m でユークリッド除算した余り) のため、このシーケンスの項は 0 とm – 1 の間になります。さらに、各項は前の項に完全に依存するため、数値がが 2 回目に表示されると、シーケンス全体がこの番号から再現されます。ここで、数値が取り得る値の数は有限 ( mに等しい) であるため、シーケンスは一定時間後に繰り返されることになります。それは最終的には周期的であると言われています。

可能性

ポテンシャルは、特定のランダム性が不十分なジェネレーターを除外することを可能にする概念です。これは常に、最大周期を持つシーケンスに対してのみ定義されます (これは、上記の 2 番目の特性に従って)。他のジェネレーターでは常にポテンシャルを定義できるわけではなく、ポテンシャルが定義されていない優れたジェネレーターもあります。

最大周期を持つシーケンスの潜在的なs は、次のような最小の整数として定義されます。

$$ {(a-1)^s \equiv 0 \mod m} $$

最大周期のシーケンスについては、X ₀ = 0 を取ることができるため、次のようになります。

$$ {X_n = \frac {a^n – 1} {a – 1} \cdot c \mod m} $$

したがって、 a ⁿ = ( (a-1) + 1 ) ⁿの場合:

$$ {X_n = c \cdot \left ( n + {n \choose 2} \cdot (a-1) + \ldots + {n \choose s} \cdot (a-1)^{s-1} \right ) \mod m} $$

ポテンシャルが 3 以下の場合は、シーケンスが十分にランダムではないため、すぐに弱すぎるように見えます。実際には、5 以上のポテンシャルが推奨されます。

ただし、可能性という概念は、少数の悪いジェネレーターを除外するためにのみ存在することを覚えておいてください。電位が 5 を超える発電機は、いかなる場合でもすぐに良好であるとは見なされず、最初にいくつかのテストを受ける必要があります。

パラメータ a、c、m の正しい選択

このタイプのアルゴリズムでは、ジェネレーターの品質は、 a 、 c 、およびmの選択に完全に依存します。これは、明確な理由もなく、X の選択に応じて多かれ少なかれランダムなシーケンスを生成するジェネレーターでは満足できないためです。 ₀ 。

悪い例

a 、 c 、 m を「ランダムに」選択するのは良い考えではありません。例を見てみましょう。
線形合同生成器 ( a =25、 c =16、 m =256) を仮定すると、次のようになります。

• X ₀ = 10の場合、シーケンス: 10, 10, 10, 10, 10, …
• _、 131、…
• _、 252、172 、…

これらのシーケンスがランダムであるとは考えられないことは明らかです。
したがって、完全なランダム性に近い数値を取得したい場合は、ジェネレーターのパラメーターを慎重に選択する必要があることが明確にわかります。

次に、 a 、 c 、 m を適切に選択する方法を自問する必要があります。

モジュールの選択

合同ジェネレーターにはモジュロm の計算が含まれるため、アプリオリなユークリッド除算が必要になります。ジェネレーターを頻繁に使用すると、計算コストが大幅に増加する可能性があります。最も簡単な解決策は、 m = 2 ^e型のモジュールを使用することです。実際、コンピュータは自然に 2 進数で計算するため、そのような選択はコンピュータにとって完全に透過的であり、ユークリッド除算は不要になります。

ただし、このような選択には重要な制限があります。いわゆる下位ビット (右端のビット) は、上位部分 (左端のビット) よりもランダム性がはるかに低いです。実際、 d がmの約数である場合、シーケンスY _{n は}次のようになります。

$$ {Y_n = X_n \mod d} $$

線形合同数列を満たす：

$$ {Y_{n+1} = (a \cdot Yn + c) \mod d} $$

特に、 d = 2 ^kの場合、1 からeまでの固定kの場合、下位k桁の最大周期は 2 ^kで、明らかに m より小さいことがわかります。
この問題を解決するには、最上位ビットのみを保持する、つまり、取得した数値の左端のビットを保持することができます。最後の k ビットを切り捨てると、0 から2 ^{e − k} − 1までの数値の擬似乱数生成器が得られます。

別の解決策は、次のタイプのモジュールを取得することで構成されます。

これにより、トリックによってユークリッド除算を回避することが可能になります (DE Knuth のThe Art Of Computer Programmingを参照)。

乗数と増分の選択

0 とm -1 の間の制約なしでシード X _{0 を}選択できるようにするには、ジェネレーターの周期を最大化するように努める必要があります。ここで、 aとcの値がわかっていることがわかり、これにより最大周期 ( mに等しい) を取得できるようになります。

線形合同生成器の周期は、次の場合にのみ最大になります。

1. まずはmからです。 Gcd(c,m) = 1。
2. m を割る素数p ごとに、(a-1) は p の倍数になります。
3. (a-1) は、m が 1 の場合、4 の倍数です。

等価定理(if および if に限り) があることに注意してください。周期は、定理の性質を持つすべての値に対して最大であり、それらの値に対してのみ最大になります。