線形合同ジェネレータ

線形合同法( LCG )は、不連続な区分線形方程式で計算された疑似乱数列を生成するアルゴリズムです。この方法は、最も古く、最もよく知られている疑似乱数生成アルゴリズムの 1 つです。その背後にある理論は比較的理解しやすく、特にストレージ ビットの切り捨てによるモジュラー演算を提供できるコンピューター ハードウェア上では、簡単に実装でき、高速です。

ジェネレータは再帰関係によって定義されます。

${\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}$

ここで、は疑似乱数の 列であり、${\displaystyle X}$

${\displaystyle m,\,0<m}$— 「係数」

${\displaystyle a,\,0<a<m}$— 「乗数」

${\displaystyle c,\,0\leq c<m}$— 「増加」

${\displaystyle X_{0},\,0\leq X_{0}<m}$— 「シード」または「開始値」

は生成器を指定する整数定数です。c  = 0の場合、生成器は乗法合同法生成器（MCG）またはLehmer RNGと呼ばれることがよくあります。c ≠ 0の場合、この方法は混合合同法生成器 と呼ばれます。^{[1] : 4-}

c ≠ 0のとき、数学者はこの再帰を線形変換ではなくアフィン変換 と呼ぶが、この誤称はコンピュータサイエンスの世界で定着している。^{[2] : 1}

レーマー生成器は1951年に発表され^[3]、線形合同生成器は1958年にWEトムソンとA.ロテンバーグによって発表されました。^{[4] [5]}

LCGの利点は、パラメータを適切に選択することで、既知の長い周期が得られることです。唯一の基準ではありませんが、周期が短すぎると、疑似乱数ジェネレーターにとって致命的な欠陥となります。^[6]

LCGは乱数に関する正式なテストに合格できる疑似乱数を生成できますが、出力の品質はパラメータmとaの選択に非常に左右されます。^{[1] [2] [7] [8] [9] [10]} たとえば、a  = 1およびc  = 1の場合、周期が長い単純なmを法とするカウンターが生成されますが、明らかにランダムではありません。cがmと互いに素な他の値の場合はワイル列が生成されますが、これはより適切に分散されますが、それでも明らかにランダムではありません。

歴史的に、aの選択が適切でなかったためにLCGの実装が非効率的になってきた。その顕著な例がRANDUである。RANDUは1970年代初頭に広く使用され、この不適切なLCGの使用により現在では疑問視されている多くの結果につながった。^{[11] [8] : 1198–9}

パラメータ選択には、次の 3 つの一般的なファミリがあります。

これはオリジナルの Lehmer RNG 構造です。乗数a がm を法とする整数の原始要素として選択される場合、周期はm −1 です。初期状態は 1 からm −1 の間で選択する必要があります。

素数を法とする欠点の 1 つは、モジュラ削減に倍幅の積と明示的な削減手順が必要になることです。多くの場合、2 のべき乗よりわずかに小さい素数が使用されるため (メルセンヌ素数2 ³¹ −1 と 2 ^{61 −1 が一般的です)、} m  = 2 ^e  −  dを法とする削減は( ax  mod 2 ^e ) +  d  ⌊ ax /2 ^e ⌋として計算できます。結果が大きすぎる場合は、この後に条件付きでmを減算する必要がありますが、減算回数はad / mに制限され、 dが小さければ 1 回に簡単に制限できます。

倍幅の積が利用できず、乗数が慎重に選択される場合は、シュラーゲ法^[12]を使用できます。これを行うには、m  =  qa + r、つまりq = ⌊ m / a ⌋およびr = m mod a を因数分解します。次に、ax  mod  m = a ( x mod q ) − r ⌊ x / q ⌋を計算します。x  mod  q < q ≤ m / aなので、最初の項はam / a  =  mよりも小さくなります。r  ≤  q (したがってr / q ≤ 1)となるようにaを選択した場合は 、2 番目の項もmよりも小さくなります: r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m。したがって、両方の積は単一幅の積で計算でき、それらの差は[1− m、  m −1]の範囲内にあるため、単一の条件付き加算で[0、 m −1]に減らすことができます 。^[13]

2 つ目の欠点は、値 1 ≤  x  <  m を均一なランダム ビットに変換するのが面倒なことです。2 の累乗よりわずかに小さい素数を使用すると、欠落している値が単に無視されることがあります。

m を2 の累乗(通常はm = 2 ³²またはm = 2 ⁶⁴ )に選択すると、 2 進表現を切り捨てるだけで係数演算を計算できるため、特に効率的な LCG が生成されます。実際、最上位ビットは通常はまったく計算されません。ただし、欠点もあります。

この形式は最大周期m /4 を持ち、a  ≡ ±3 (mod 8) かつ初期状態X ₀が奇数の場合に達成されます。この最良の場合でも、Xの下位 3 ビットは2 つの値の間で交互に変化するため、状態に寄与するのは 1 ビットのみです。X は常に奇数 (最下位ビットは変化しない) であり、次の 2 ビットのうち 1 つだけが変化します。a ≡ +3 の場合、  Xは±1↔±3 に交互に変化し、 a ≡ −3の場合 、X は±1↔∓3 に交互に変化します (すべて 8 を法とする)。

この形式は、係数m /4およびc ≠ 0を持つジェネレータと同等であることが示される。^[1]

2 のべき乗の法を使用する場合のより深刻な問題は、下位ビットの周期が上位ビットよりも短いことです。実装が簡単なのは、ビットが上位ビットの影響を受けないことから来ており、このようなジェネレータの下位bビットは、それ自体で 2 ^{b −2の周期で繰り返される modulo-2 b} LCG を形成します。Xの最上位ビットのみが完全な周期を達成します。

c ≠ 0のとき、正しく選択されたパラメータは、すべてのシード値に対してmに等しい周期を許容します。これは、次の場合にのみ発生します: ^{[1] : 17–19}

1. ${\displaystyle m}$互いに素であり、${\displaystyle c}$
2. ${\displaystyle a-1}$は のすべての素因数で割り切れる。${\displaystyle m}$
3. ${\displaystyle a-1}$が 4 で割り切れる場合、は 4 で割り切れます。${\displaystyle m}$

これら3つの要件はハル・ドーベル定理と呼ばれています。^{[14] [15]}

この形式は任意のmで使用できますが、2 の累乗など、多数の繰り返し素因数を持つmに対してのみ適切に機能します。コンピュータのワード サイズを使用するのが最も一般的な選択です。m が平方のない整数である場合、これはa  ≡ 1 (mod  m )のみを許可し、非常に貧弱な PRNG になります。可能な全周期乗数を選​​択できるのは、 m に繰り返し素因数がある 場合のみです。

ハル・ドーベル定理は最大周期を与えるが、それだけでは良い生成器を保証するのに十分ではない。^{[8] : 1199} たとえば、a − 1 は必要以上にm の素因数で割り切れないことが望ましい。mが2 の累乗であれば、a  − 1 は 4 で割り切れるが 8 で割り切れない、つまり a  ≡ 5 (mod 8) でなければならない。^{[1] : §3.2.1.3}

実際、ほとんどの乗算器は、非ランダム性テストのいずれかに失敗するシーケンスを生成し、すべての適用可能な基準^{[1] ：§3.3.3}を満たす乗算器を見つけることは非常に困難です。^[8] スペクトルテストは最も重要なテストの1つです。^[16]

2 のべき乗を法とする場合には、c  = 0 の場合に上記で説明した問題と同じ問題が発生することに注意してください。つまり、下位kビットは 2 ^kを法とするジェネレータを形成し、周期 2 ^kで繰り返します。最上位ビットのみが全周期を達成します。 r未満の疑似乱数が必要な場合、⌊ rX / m ⌋ はX mod rよりもはるかに高品質の結果になります。残念ながら、ほとんどのプログラミング言語では後者の方がはるかに簡単に記述できるX % rため ( )、非常に一般的に使用されています。

ジェネレータは、 c が係数と互いに素である限り、cの選択には影響されません(たとえば、 m が2 の累乗である場合、c は奇数である必要があります)。そのため、通常はc =1 という値が選択されます。

cの他の選択によって生成されるシーケンスは、c =1 のときのシーケンスの単純な関数として記述できます。 ^{[1] : 11} 具体的には、YがY ₀ = 0 およびY _{n +1} =  aY _n + 1 mod mで定義されるプロトタイプシーケンスである場合 、一般的なシーケンスX _{n +1} =  aX _n  +  c mod  m はYのアフィン関数として記述できます。

${\displaystyle X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.}$

より一般的には、同じ乗数と係数を持つ任意の 2つのシーケンスXとZは、

${\displaystyle {X_{n}-X_{0} \over X_{1}-X_{0}}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}}{\pmod {m}}.}$

mが 2 の累乗でa ≡ 5 (mod 8)である一般的なケース (他の理由から望ましい特性) では、分母X ₁  −  X ₀ ≡ ±1 (mod  m ) となる初期値X ₀を見つけることが常に可能であり、さらに単純な関係が生成されます。このX ₀の選択により、X _n =  X ₀  ±  Y _{n は}すべてのnに対して成り立ちます。^{[2] : 10-11}符号はc  ≡ ±1 (mod 4) によって決定され、定数X ₀は 1 ∓  c  ≡ (1 −  a ) X ₀  (mod  m ) によって決定されます。

簡単な例として、ジェネレータX _{n +1} = 157 X _n  + 3 mod 256 とY _{n +1} = 157 Y _n  + 1 mod 256、つまりm  = 256、a  = 157、c = 3 を考えます。3 ≡ −1 (mod 4) なので、1 + 3 ≡ (1 − 157) X ₀ (mod 256) の解を探しています。これはX ₀ ≡ 41 (mod 64) で満たされる ので、そこから始めると、すべてのnに対してX _n ≡  X ₀  −  Y _n  (mod 256) になります。

たとえば、X ₀ = 233 = 3×64 + 41 を使用すると、

• X = 233、232、75、2、61、108、...
• Y = 0、1、158、231、172、125、...
• X  +  Y mod 256 = 233、233、233、233、233、233、...

次の表は、さまざまなコンパイラのランタイムライブラリに組み込まれているrand()関数を含む、一般的に使用されているLCGのパラメータを示しています。この表は人気を示すためのものであり、エミュレートするための例ではありません。これらのパラメータの多くは貧弱です。 適切なパラメータの表が利用可能です。^{[10] [2]}

上で示したように、LCG は生成する値のすべてのビットを常に使用するわけではありません。一般的には、最上位ビットを返します。たとえば、Java実装は各反復で 48 ビットの値で動作しますが、最上位 32 ビットのみを返します。これは、上位ビットの周期が下位ビットの周期よりも長いためです (下記参照)。この切り捨て手法を使用する LCG は、使用しない LCG よりも統計的に優れた値を生成します。これは、範囲を縮小するために mod 演算を使用するスクリプトで特に顕著です。乱数を mod 2 で変更すると、切り捨てなしで 0 と 1 が交互に表示されます。

逆に、一部のライブラリでは、暗黙的な 2 の累乗の係数を使用しますが、出力を正の2 の補数の整数に制限するために、最上位ビットを出力したり使用したりすることはありません。出力は、係数が内部ワード サイズより 1 ビット少ない場合と同じであり、このようなジェネレータは上記の表でそのように説明されています。

LCG は高速で、状態を保持するために最小限のメモリ (1 つのモジュロm数、多くの場合 32 ビットまたは 64 ビット) しか必要としません。このため、LCG は複数の独立したストリームをシミュレートするのに適しています。LCG は暗号化アプリケーション用には意図されておらず、使用してはなりません。このようなアプリケーションには、暗号化された安全な疑似乱数ジェネレータを使用してください。

LCG にはいくつかの特定の弱点があるが、その欠陥の多くは状態が小さすぎることに起因している。人々が長年、このような小さなモジュラスで LCG を使用するように誘導されてきたという事実は、この技術の強さの証しと見ることができる。十分に大きな状態を持つ LCG は、厳しい統計テストにも合格することができる。上位 32 ビットを返すモジュロ 2 ^{64 LCG は、} TestU01の SmallCrush スイートに合格し、^{[引用が必要]}、96 ビット LCG は最も厳しい BigCrush スイートに合格する。^[35]

具体的な例として、出力が 32 ビットの理想的な乱数ジェネレータは、（バースデイ定理により）√ m ≈ 2 ^{16 の}結果の後に以前の出力を複製し始めると予想されます。出力が完全で切り捨てられていない状態であるPRNG は、その全周期が経過するまで複製を生成しません。これは簡単に検出できる統計的欠陥です。^{[36]関連する理由から、PRNG の周期は必要な出力数の 2 乗よりも長くする必要があります。現代のコンピュータ速度を考えると、これは、最も要求の少ないアプリケーションを除くすべてのアプリケーションで 2 64} の周期を意味し、要求の厳しいシミュレーションではさらに長くなります。

LCG に特有の欠点の 1 つは、n 次元空間で点を選択するために使用した場合、点は最大でⁿ √ n !⋅ m 個の超平面上に存在することになる(ジョージ・マルサリアが考案したマルサリアの定理) ことです。^{[7]これは、シーケンス}X _nの連続する値間のシリアル相関によるものです。不注意に選択された乗数は、通常、はるかに少ない、間隔の広い平面を持ち、問題を引き起こす可能性があります。LCGの品質を簡単にテストするスペクトル テストでは、この間隔を測定し、適切な乗数を選択できるようにします。

平面間隔は、係数と乗数の両方に依存します。十分に大きい係数は、この距離を倍精度数の解像度以下に短縮できます。係数が大きい場合、乗数の選択はそれほど重要ではありません。スペクトル指数を計算し、乗数が不適切なものでないことを確認する必要はありますが、純粋に確率的に、係数が約 2 ⁶⁴より大きい場合、不適切な乗数に遭遇する可能性は極めて低くなります。

LCG に特有のもう 1 つの欠陥は、 mが 2 の累乗に選択された場合に下位ビットの周期が短くなることです。これは、必要な出力よりも大きい係数を使用し、状態の最上位ビットを使用することで軽減できます。

それでも、一部のアプリケーションでは LCG は適切な選択肢となる場合があります。たとえば、組み込みシステムでは、使用可能なメモリの量が厳しく制限されることがよくあります。同様に、ビデオ ゲーム コンソールなどの環境では、LCG の上位ビットを少し使用すれば十分でしょう。(m が 2 の累乗である場合の LCG の下位ビットは、いかなる程度のランダム性にも決して依存すべきではありません。) 下位ビットは非常に短いサイクルを経ます。特に、m が 2 の累乗である場合のフルサイクル LCG は、奇数と偶数の結果を交互に生成します。

LCG は、高品質のランダム性が重要となる非暗号化アプリケーションに適しているかどうかを慎重に評価する必要があります。モンテ カルロ シミュレーションの場合、LCG は、必要なランダム サンプルの数の 3 乗よりも大きい、できればそれよりはるかに大きい係数を使用する必要があります。つまり、たとえば、(適切な) 32 ビット LCG を使用すると、約 1,000 個の乱数を取得できます。64 ビット LCG は、約 2 ^{21 個の}ランダム サンプル (200 万を少し超える) に適しています。このため、実際には LCG は大規模なモンテ カルロ シミュレーションには適していません。

以下は、ジェネレーターの形式でPythonで LCG を実装したものです。

 collections.abc からジェネレータをインポート 

def  lcg ( modulus :  int ,  a :  int ,  c :  int ,  seed :  int )  ->  Generator [ int ,  None ,  None ]: 
"""線形合同型ジェネレータ。""" while True : seed = ( a * seed + c ) % modulus yield seed    
     
                
         

以下は、遅延評価戦略を利用してリスト内に出力値の無限ストリームを生成する Haskellでの LCG の実装です。

-- a、c、m、x_0 の一般的な選択を許可
linearCongruentialGenerator :: Integer -> Integer -> Integer -> Integer -> [ Integer ] linearCongruentialGenerator a c modulus seed = lcgacmx0 where lcgacmx0 = seed : map ( \ x -> ( a * x + c ) % modulus ) lcgacmx0          
      
               

-- 特定のパラメータを簡単に指定できます (例: Knuth の MMIX パラメータ): 
mmixLCG :: Integer -> [ Integer ] mmixLCG = linearCongruentialGenerator 6364136223846793005 1442695040888963407 ( 2 ^ ( 64 :: Integer ))    
      

Free Pascal はデフォルトの疑似乱数生成器としてメルセンヌツイスターを使用しますが、Delphi は LCG を使用します。これは、上記の表の情報に基づいた、 Free Pascalでの Delphi 互換の例です。同じ RandSeed 値を指定すると、Delphi と同じ乱数シーケンスが生成されます。

ユニットlcg_random ; {$ifdef fpc}{$mode delphi}{$endif}インターフェース 



関数LCGRandom :拡張;オーバーロード;インライン;関数LCGRandom ( const range : longint ) : longint ;オーバーロード;インライン;    
     

実装
関数IM : cardinal ; inline ; begin RandSeed := RandSeed * 134775813 + 1 ; Result := RandSeed ; end ;   

        
    


関数LCGRandom :拡張;オーバーロード;インライン;開始結果:= IM * 2.32830643653870e-10 ;終了;    

      


関数LCGRandom ( const range : longint ) : longint ;オーバーロード;インライン;開始Result := IM * range shr 32 ;終了;      

        

すべての疑似乱数ジェネレータと同様に、LCG は状態を保存し、新しい数値を生成するたびに状態を変更する必要があります。複数のスレッドが同時にこの状態にアクセスすると、競合状態が発生する可能性があります。実装では、同時に実行されるスレッドで乱数のシーケンスが均等にならないように、スレッドごとに固有の初期化を持つ異なる状態を使用する必要があります。

異なる形式の線形合同型ジェネレーターであるジェネレーターがいくつか存在するため、LCG を分析するために使用される手法をそれらに適用できます。

より長い周期を生成する方法の 1 つは、大きな最小公倍数を持つ異なる周期の複数の LCG の出力を合計することです。この形式の例には、ヴィッヒマン–ヒル生成器があります。(これらが完全に互いに素であることが望まれますが、素数の係数は偶数周期を意味するため、少なくとも 2 の共通因数がなければなりません。) これは、LCG の構成要素の係数の積に等しい係数を持つ単一の LCG と同等であることが示されます。

マルサリアの桁上げ加算および桁下げ減算PRNGは、ワードサイズがb =2w^でラグrとs（r  >  s）であり、係数がb ^r  ±  b ^s  ± 1のLCGと同等である^{。[37] [38]}

乗数aを持つ乗算と繰り上がりPRNG は、大きな素数係数ab ^r −1 と 2 の累乗乗数bを持つ LCG と同等です。

置換合同型ジェネレータは、 2の累乗係数 LCG から開始し、出力変換を適用して、下位ビットの短期問題を排除します。

長周期疑似乱数列を得るために広く使われているもう1つのプリミティブは、 GF(2)上の多項式環であるGF(2)[ x ]の演算に基づく線形フィードバックシフトレジスタ構成である。整数加算や乗算ではなく、基本演算は排他的論理和とキャリーレス乗算であり、通常は論理シフトのシーケンスとして実装される。これらには、すべてのビットが全周期であるという利点があり、 ^2kを法とする演算で問題となる下位ビットの弱点の影響を受けない。^[39]

このファミリーの例には、排他的論理和シフト生成器とメルセンヌツイスターが含まれます。後者は非常に長い周期（2 ¹⁹⁹³⁷ −1）と変量の均一性を提供しますが、いくつかの統計的テストに失敗します。^[40] 遅延フィボナッチ生成器もこのカテゴリに分類されます。算術加算を使用しますが、その周期は最下位ビット間のLFSRによって保証されます。

線形フィードバックシフトレジスタの構造は、TestU01スイートに実装されている線形複雑度テストなどの適切なテスト^[41]で簡単に検出できます。LFSRの連続ビットから初期化されたブール巡回行列のランクは、多項式の次数を超えることはありません。非線形出力混合関数（ xoshiro256**や置換合同型ジェネレータ構造など）を追加すると、統計テストのパフォーマンスが大幅に向上します。

PRNG のもう 1 つの構造は、非常に単純な再帰関数と強力な出力混合関数を組み合わせたものです。これには、カウンター モードブロック暗号や SplitMix64 などの非暗号化ジェネレーターが含まれます。

LCG に似ているが同等ではない構造は、多重再帰ジェネレーターです。X _n  = ( a ₁ X _{n −1}  + a ₂ X _{n −2}  + ··· + a _k X _{n − k} ) mod  m ( k  ≥ 2)。素数係数を使用すると、これはm ^k −1 までの周期を生成できるため、LCG 構造をより大きな周期に拡張するのに便利です。

高品質の疑似乱数を生成する強力な手法は、異なる構造の 2 つ以上の PRNG を組み合わせることです。LFSR と LCG ( KISSまたはxorwow構造の場合) の合計は、速度が多少犠牲になりますが、非常に優れた結果をもたらします。

• 乱数ジェネレーターのリスト- 統計品質が優れているものを含むその他のPRNG
• ACORNジェネレーター- LCGおよびLFSRジェネレーターの変種に使用されていたと思われるACGと混同しないでください。
• 順列合同ジェネレータ
• フルサイクル
• 逆合同法ジェネレータ
• 繰り上がり乗算
• Lehmer RNG (Park–Miller RNG とも呼ばれる)
• 複合線形合同ジェネレータ

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 7.1.1. いくつかの歴史」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8、2011-08-11にオリジナルからアーカイブ、2011-08-10に取得
• Gentle, James E., (2003).乱数生成とモンテカルロ法、第 2 版、Springer、ISBN 0-387-00178-6。 
• Joan Boyar (1989). 「疑似乱数ジェネレータによって生成されたシーケンスの推測」(PDF) . Journal of the ACM . 36 (1): 129– 141. doi :10.1145/58562.59305. S2CID  3565772.(この論文では、特定の疑似乱数ジェネレータによって生成されたシーケンスを推測するための効率的なアルゴリズムが示されています)。

• 線形合同ジェネレーターのシミュレーションは、パラメータを操作するときに疑似乱数間の相関関係を視覚化します。
• 乱数生成のセキュリティ: 注釈付き参考文献
• 線形合同型ジェネレーターを sci.math に投稿
• Goldstein Technologies LLC の「Death of Art」コンピュータ アート プロジェクトでは、LCG を使用して 33,554,432 枚の画像を生成します。
• P. L'Ecuyer および R. Simard、「TestU01: 乱数ジェネレーターの実証的テスト用 AC ライブラリ」、2006 年 5 月、2006 年 11 月改訂、ACM Transactions on Mathematical Software、33、4、記事 22、2007 年 8 月。
• LCG を解読する別の方法についての記事