スマートフォン用の表示で見る

線形合同法

サイエンス

線形合同法

せんけいごうどうほう

擬似乱数に使われる計算式。

乱数としてはあまり質がよくないが、簡易なのでよく使われる。

英語で、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より]

abm
Numerical Recipes16645251013904223232
Borland C/C++226954771232
glibc (used by GCC)110351524512345232
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++110351524512345232
Borland Delphi, Virtual Pascal1347758131232
Microsoft Visual/Quick C/C++ 2140132531011232
Apple CarbonLib168070231-1

これらは全て、2進数で使われることを想定している。


欠点は:周期が短い・分布が線形である・予測可能である(暗号には使えない)

利点は:生成は極めて高速である・アルゴリズムが簡易である