線形合同法
(サイエンス)
【せんけいごうどうほう】
擬似乱数に使われる計算式。
乱数としてはあまり質がよくないが、簡易なのでよく使われる。
英語で、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進数で使われることを想定している。
欠点は：周期が短い・分布が線形である・予測可能である（暗号には使えない）
利点は：生成は極めて高速である・アルゴリズムが簡易である
