はてなキーワード 線形合同法

keyword:線形合同法を書いたので、勢い余って転載。

keyword:線形合同法


英語で、linear congruential generator (LCG)。
乱数列の生成方法は、漸化式で、

x0 = Seed
xn = (axn-1 + b) mod m

である。a、b、mは定数。


周期は高々mであり、

bとmは互いに素
a-1が、mの全ての素因数で割り切れる
mが4の倍数の場合、a-1も4の倍数である
m > xn
以上4つの条件が満たされるとき、周期は最大値mとなる。
それぞれの数は下位ビットであるほど周期が短く、最下位ビットは高々2である。
一般に、下からnビット目の周期は高々2nである。


mには、乱数を必要とする環境での基数の累乗を設定すると、得られた数値を使用しやすい。
通常の、ビット単位で用いる、2進数では2n
10進数では10nといった具合である。
また乱数の種に現在時刻などの偏りやすい数値を用いる場合、乱数列の始めの100個程度は捨てるべきである。


a, b, mの例
[http://en.wikipedia.org/wiki/Linear_congruential_generatorより]

    

    
 
    
a
    
b
    
m
    
    

    
Numerical Recipes
    
1664525
    
1013904223
    
232
    
    

    
Borland C/C++
    
22695477
    
1
    
232
    
    

    
glibc (used by GCC)
    
1103515245
    
12345
    
232
    
    

    
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++
    
1103515245
    
12345
    
232
    
    

    
Borland Delphi, Virtual Pascal
    
134775813
    
1
    
232
    
    

    
Microsoft Visual/Quick C/C++
    
	214013
    
2531011
    
232
    
    

    
Apple CarbonLib
    
16807
    
0
    
231-1
    
これらは全て、2進数で使われることを想定している。


欠点は：周期が短い・分布が線形である・予測可能である（暗号には使えない）
利点は：生成は極めて高速である・アルゴリズムが簡易である

JavaScriptでの線形合同法を実装した時には、自分は、10進数用で、

• a = 421
• b = 3
• m = 1e+16

にして、始めの100個は捨てます。
以下↓

線形合同法でJS Nativeに勝った！
　http://d.hatena.ne.jp/Kureduki_Maari/20090121/1232523689