線形合同法
Linear Congruential Generator
初期値$ x_1をシード値として、漸化式で$ x_2, x_3, ...を生成していく伝統的な疑似乱数生成アルゴリズムの一つ。
長所
非常に軽量で高速
漸化式のパラメータを記憶するための最低限のメモリがあればよい
剰余部分はビットシフトを用いて高速化できる
実装が簡単
理解も簡単
欠点
線形合同法の下位ビットのランダム性が悪い
偶数で割ったあまりを利用すると奇数と偶数が交互に出る
上位ビットを切り取って利用するとマシになる
タプルとして順番に生成列を割り当て、座標系にプロットすると非常に規則的に見える
高次元均等分布性？
http://maya.phys.kyushu-u.ac.jp/~knomura/education/numerical-physics/text7/node4.html
周期は$ Mの値に依存する。
32bitシステムなら最大$ 2^{32} - 1