More than 3 years have passed since last update.

1103515245

Last updated at 2020-12-07Posted at 2020-12-06

LCG

この記事はkb Advent Calendar 2020 5日目の記事です。 https://adventar.org/calendars/5280

rand()

C言語のrand()は線形合同法(LCG)が用いられていると書かれていることがあるが、BSD libcやglibcのrand()の内部で使われているrandom()では、線形合同法を用いたTYPE_0、及び線形帰還シフトレジスタを用いた内部状態のサイズごとTYPE_1~TYPE_4の計5タイプの乱数生成器が存在する。

この乱数生成器のタイプは、initstate()で設定された初期状態のサイズによって決まり、状態が8/32/64/128/256byteごとにTYPE_0~TYPE_4の乱数生成器が用いられる。

initstate()の結果が32未満の場合、つまりTYPE_0の場合は線形合同法が用いられる。(glibcの場合は3回行い全ビット、ANCI Cなどでは上位16ビットが出力される)

それ以外の場合はrandom()は線形帰還シフトレジスタが用いられる。

srand()を実行してシードを設定した状態ではデフォルトで128byteとなるためTYPE_3が用いられることになる。

TYPE_3ではサイズが31の内部状態を用いて線形帰還シフトレジスタを用い、下位1ビットを右シフトで捨てたものが取得できる。また、その内部状態はrandの出力を観測することによって予測が可能である。参考: Z3Pyでglibc rand(3)の出力を推測してみる

また、glibcで用いられている線形帰還シフトレジスタの解説は以下が詳しい。
The GLIBC random number generator

今回はこちらではなく、TYPE_0の実装に用いられている線形合同法の初期パラメータとして使用されている1103515245という数字についてである。

線形合同法

線形合同法は漸化式

$xn+1=(A×xn+C)modM$

で表され、定数 $A,C,M$ 、及び $x0$ を設定し疑似乱数を生成出来るというものである。

ここで、周期性が大きくランダム性のある乱数生成器を生成するためには、上記の定数を注意深く選ぶ必要があり、歴史的にはAの選択があまり良くなかったためにLCGの実装であまり効果が良くなかったケースが多く、計算速度は相当速いが精度の悪いIBM社のRANDUというサブルーチンなどが有名である。

パラメータの選択の方法は大まかにc=0以下の3パターンがある。

c = 0、Mが素数
c = 0、Mが2の累乗
c != 0 かつ以下をすべて満たす
- CとMが互いに素(最大公約数が11)
- A−1がMの全ての素因数で割り切れる
- Mが4の倍数ならばA−1も4の倍数

c = 0、Mが素数

これは1948年にレーマーが発表した乗算合同法である。minstd_randなどはこちらで実装されている。

c = 0、Mが2の累乗

割り算をシフトレジスタのみで出来るのでパフォーマンスに優れるが、下位ビットの周期が上位ビットよりも短いことが欠点である。
RANDUや、古い実装ではこちらで実装されていた。

c != 0 かつ条件をすべて満たす

CとMが互いに素(最大公約数が11)
A−1がMの全ての素因数で割り切れる
Mが4の倍数ならばA−1も4の倍数

Hull-Dobell定理として知られる上記の条件を満たすことで、すべてのシード値(!=0)において、最大値Mの周期を得ることが可能となる。

参考:疑似乱数についてその1 線型合同法の最大周期条件

パラメータ選び

コンピュータで線形合同法を用いる場合、前述のHull-Dobell定理を満たすパラメータの中で乗数$A$・加数$C$の選び方として、乗数$A$のコストがなるべく少なく(係数の平方根に近い乗数)、かつ統計的に優れた乗数を選ぶ必要がある。効果的なパラメータの例

1103515245

libcやglibcなど、色んな場所で使用されているa=1103515245/c=12345という数字がいつ現れたかについて分からなかったが(色々調べたけど)、Version 7 Unixから既に存在している。この値は他の値に比べてあまり乱数的に優れてはおらず、ビットごとに周期性があり、最下位ビットは周期2、次のビットは周期4という規則性があるため、実質$2^8$程度くらい(らしい)

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up