はじめに
備忘録も兼ねて，大学の講義で勉強した内容をまとめます．
擬似乱数とは？
- コンピュータが生成する乱数
- ソフトウェアで扱っている乱数は，実は完全なランダムではない
- とあるアルゴリズムに従って生成
- 周期が存在する
- 計算式と初期値が分かれば同じ乱数列を再現できる
線形合同法について
線形合同法(Linear Congruential Generator:LCG)は，擬似乱数生成アルゴリズムの中で最もポピュラーで簡単なもの，ポケモンをはじめ様々なゲームで使われている乱数．
生成式は以下
$x_{n+1} = (A \times x_n + C) mod M$
初期値の$A$, $C$, $M$, $x_0$が決まればあとは上の漸化式に当てはめて生成ができる．
線形合同法の生成周期について
- 周期の最大は$M$
- 条件(全て満たして周期が最大になる)
- $C$と$M$が互いに素(最大公約数が$1$)
- $A-1$が$M$の全ての素因数で割り切れる
- $M$が$4$の倍数ならば$A-1$も$4$の倍数
- 条件(全て満たして周期が最大になる)
計算例
手計算するのは面倒なのでPythonのプログラムに計算を任せます(怠惰)
計算プログラムは以下
#coding:utf-8
A, C, M = map(int, input().split())
# 初期値の入力
x = int(input())
cnt = 0
# 最大周期を確認するためにrangeはM+1に設定
for i in range(M+1):
print('x%d: %d' % (cnt, x))
x = (A * x + C) % M
cnt += 1
(...もっと賢い書き方があったかもしれないですが目を瞑ってください)
- 周期が最大にならない例と実行結果
$A=3, C=4, M=11, x_0=1$として実行してみます．
3 4 11
1
x0: 1
x1: 7
x2: 3
x3: 2
x4: 10
x5: 1
x6: 7
x7: 3
x8: 2
x9: 10
x10: 1
x11: 7
初期値$1$からスタートして，$x_5$でまた計算結果が$1$になるので周期は$5$ということになります．この例では「$A-1$が$M$の全ての素因数で割り切れる」という条件を満たしていないので，周期が最大にならないということが分かります．
- 周期を最大($M$)にする例と実行結果
$A=13, C=5, M=12, x_0=1$として実行してみます．
13 5 12
1
x0: 1
x1: 6
x2: 11
x3: 4
x4: 9
x5: 2
x6: 7
x7: 0
x8: 5
x9: 10
x10: 3
x11: 8
x12: 1
初期値$1$からスタートして，$x_{12}$でまた計算結果が$1$になるので周期は$12$，つまり$M$ということになります．
線形合同法の弱点
最大周期の例の計算結果を見ると分かりますが，割る数(ここでいうところの$M$)が偶数の場合，乱数は奇数と偶数がそれぞれ交互で生成されてしまいます．
「カルドセプトサーガ」というすごろくのようなゲームでこの仕様を知らずに乱数プログラムを実装した結果次に出るダイスの目が奇数か偶数かが推定できてしまうバグを生み出してしまったようです．
すごろくゲームでダイスの目が事前に分かってしまうのは致命的ですね...
#おわりに
勉強した範囲内ではありますが線形合同法についてざっとまとめてみました．
もし説明不足や間違った記述がありましたら指摘してくださると助かります．
乱数生成アルゴリズムには線形合同法の他にもメルセンヌ・ツイスタ法やxorshiftなどもあるみたいです，余力があればいつか勉強してまとめたいです．
#参考リンク
- Algoful - 線形合同法 ( http://algoful.com/Archive/Algorithm/LCG )