忘れん坊の備忘録

情報工学科に通う大学生のメモ。あまり詳しくは無いです。備忘録として殴り書き

擬似乱数について軽くまとめる

大学の授業にて乱数について教わりました

これが結構面白いし、今後の役に立ちそうなので忘れないように記述します


初歩的な話からすると、プログラムでの乱数生成は結構難しい
どうやって計算でランダムな値を出すかというのは簡単にはできないことです。

しかも、精度の高い偏りの無い乱数っていうものは大変なわけです
自分で偏りのないランダムな数字を計算で出してくださいって言われたら普通に無理って思います。



パソコンで生成される乱数はランダムに見えるけど、実は周期のある数列になります。
この乱数のことを「擬似乱数」と呼びます。

周期はあるんですが、かなり長いため実質ランダムだよねというのが擬似乱数の仕組みなわけです。




一番単純な擬似乱数生成アルゴリズムとしては "線形合同法” があります

このアルゴリズムは単純で高速に生成できるんですが、いろいろ問題があります
Xnが決まるとXn+1が決まってしまったり、パラメータを使うときに推奨値を使わないといけなかったり
とにかくあまりよくない方式です

C言語で使うrand()なんてのはこれの亜種が使われてます。(遅れフィボナッチ法?)
これだとXnが決まってもXn+1が決まらないようになってるそうです(よく知らない・・・)

C言語の乱数はseedが同じだと同じ乱数列が返ってきてしまいますよね
これはあまり良くないですが、実験を行う際などにはseed固定してバグを確認出来るので便利ではあります。


ここまでの乱数は割と良くない乱数なのであんまり使わない方が良いです

ってことで実用的な話をしていきましょう

今回話すのは2つ!
Mersenne Twister(MT)
・xorshift
です!!

Mersenne Twister(MT)

このアルゴリズムは今現在最も良い擬似乱数生成アルゴリズム!!(この改良版としてSFMTが出ていますが、ここでは同じものとして考えます)
・周期が長い!→(2^19937)-1
・結構、生成速度も早い!
・均等な分布で数値が出る!!(メモ:623次元超立方体で均等分布が保証されているとか言ってたけど良くわからなかった)

pythonはこのアルゴリズムが使われてるって聞いたことがある気がします(確証ないけど)
詳しい式が気になる人は調べてもらうと良いかなと思います。
(xorとか行列とかの式だったと思う)

以下のページが正式なホームページなので気になる方はどうぞ
Mersenne Twister: A random number generator (since 1997/10)

#xorshift

このアルゴリズムの良い点は
・めっちゃ単純
・めちゃくそ早い
・その割に精度良い!
みたいな感じです。
要はMTよりは精度良くないけど、早いし簡単にできて、精度もそれなりなんでコスパが良いってことです。
xorとシフトを使うだけで擬似乱数が生成できるという素晴らしさ

JavaScriptはこのアルゴリズム使ってるとか聞いた気がする

ついでにMT作った人たちが、このアルゴリズムに改良加えているサイトがあるのでこちらも参考に
XORSHIFT-ADD (XSadd)



軽くまとめたので、今後思い出す時の参考ぐらいかなぁ
実装自分でしてみるのも楽しいそう



ついでに良く使うC#の乱数アルゴリズム知らないなと思って調べました
"Knuthの差分乱数ジェネレータ"

知らないアルゴリズム出てきた・・・
これは、また今度調べます・・・。