今回の話題

人類にMTはでかすぎる

疑似乱数とは

コンピュータでは擬似乱数しか作ることは出来ません。
本の1ページ毎にランダムな数字が書いてあり、1ページずつ読み進める感じです。
もし同じ本を持っていて、同じページから進めれば、
全く同じ乱数となります。

レトロゲーのRTAだと状況再現と言うテクニックがあります。
電源ONからの入力を完全に同じようにすることで、同じページからすすめるようにして
敵の出現やダメージまで完全に過去と同じにする方法です。

メルセンヌ・ツイスタ(以下MT)は今の所万能と言われる乱数です。
MTの乱数の本のページ数は2^19937-1、桁数にすると6000桁。
宇宙に存在する原子の数の予想が80桁ですから
宇宙が75個ほどあってようやく一周するほどの巨大な本です。

嘘です。
桁数同士の比較ですから、まだ5920桁個の宇宙が必要です。
でかすぎる！

さて、大きすぎる数の話なので、2進数の桁数と言う意味でbitという表現を使います。
例えば、16bitなら(2進数で)16桁の数という意味です。

この巨大な本、読み始める場所が決まっています。
栞みたいなのが入っているページのみから始められ、大体32bit(42億)通りしかありません
この始めるページをシードと言います。

42億もあるんだから、十分じゃんと思うのですが、
同じページから始める人がいるかどうかだけなら6万回試行するだけでどこかは被ります

さらに、乱数を何個ぐらい使うかを考えると、
1秒に100個生成して1年使うと大体32bit程度の数になります。

つまり、入り口が32bitで使うページが32bitなので、
大体64bitのページを使うことになります。

これはMTの全体に対すると、1/(19873bit)です。
冒頭に上げたとおり宇宙の原子の数を持ってきても比較できないサイズなので、
人類が使っている部分なんてほんの一部…という表現も大きすぎるレベルです。。

つまり誰も見たこともないページがめちゃくちゃあるわけです。
そのために今何ページ目を読んでいるか、という情報が内部的にあるわけで、
具体的には19937bit分のデータ、ページ数を表すだけで約2.5kbのメモリを消費するわけです。

今のPCだと大した量ではないんですが、
使いもしないメモリを消費しているわけで無駄といえば無駄です。

そこで、何がおすすめなの？と言われれば、Xorshift128です。
周期が2^128-1、64bitの数として取り出しても64bitの周期があります。
メモリ消費も32byte、人類が使うであろうサイズにジャストフィットです。