疑似乱数生成器
MTToolBox
MTToolBox というのは、疑似乱数生成器を開発する際に利用できるツールである。これを公開したら、卒論や修論で疑似乱数生成器を作る人が続出して、様々な疑似乱数生成器が乱立し、どれがよいのやら速いのやらまったく分からなくなって世の中が混乱すると思ったのだが、全然そんなことにはなっていないのであった。
これはMTToolBoxの機能に不足があるからに違いない。SFMTを作るときに使った機能がMTToolBoxには入っていないのである。その機能とはいわゆるReducible Generatorの作成機能である。
MTToolBox: メインページ
GF(2)線形疑似乱数生成器とMersenne Twister
MTToolBox はGF(2)線形疑似乱数生成器の開発をサポートするC++のライブラリなのだ。その辺のことは、スライドhttp://msaito.github.io/MTToolBox/mttoolbox.pdfを見て欲しい。GF(2)というのは二元体、ゼロとイチの四則演算が出来る世界で、疑似乱数生成器が線形というのは状態遷移関数と出力関数が線形ということである。読者の前提知識が分からないと説明が面倒だ。
それはともかく、シミュレーション用の疑似乱数生成器では周期が重要なのである。何はともあれ周期を保証する必要がある。もちろん、周期というのは最低周期である。最大周期ではない。時々勘違いしている人がいるので念のため。使用メモリから最大周期はすぐに分かるのだが、最低周期は計算する必要がある。その計算過程で、素因数分解が必要になるのが問題なのである。
Mersenne Twister の発想の優れたところは、素数と分かっていれば素因数分解必要ないじゃんというところである。まあ、それだけじゃないけど、それは重要なのである。MTToolBoxはMersenne Twister タイプの周期がメルセンヌ素数になる疑似乱数生成器の開発をサポートする機能がある。
まあ、大雑把に言うと、状態遷移関数の線形写像の特性多項式の次数がメルセンヌ指数（メルセンヌ素数の指数部）で、かつ、それが既約多項式であれば、状態遷移の周期はメルセンヌ素数になる。
そのために、Mersenne Twisterでは欠けた配列を使っている。メモリの一部を敢えて使わないことによって、特性多項式の次数がメルセンヌ指数になる（なりやすい）ようにしている。
W0の右側は使っていないのである。メモリがちょっともったいないけど、メモリはたくさんあるから31ビットくらい無駄にしても大したことはない。しかし、メモリ自体は問題ないのだが、欠けた配列の場合、最終防衛ラインともいうべきものが二段になってしまうという問題がある。説明は数学的に難しいという訳ではないが、説明されて分かる人なら説明されなくても分かるような気がするので、説明しないのだが、「最終防衛ラインの全ビットを次状態の計算に使用しなければならない」という制約がある。
この制約のために、CPUの命令が少なくとも二つ余分に使われる。メモリロードも入れると更に増える。つまりAND命令でマスクして使わない部分をゼロにする。二段目とORまたはXORする。という二つである。
二段目の左側は参照しても参照しなくてもよいが、参照するならORではなくXORする必要がある。もともと、Mersenne Twister の状態遷移に使用するCPU命令は多くないので、ここで二つ使ってしまうのは惜しい。
SFMT(とdSFMT)
ところで、SFMTでは欠けた配列を使っていない。
そうすると最終防衛ラインは一段で、マスクする必要も二段目とXORする必要もない。って、周期を保証するために状態空間がメルセンヌ指数ビットである必要があるって言ったやんか。どうなってるんや。実は、状態遷移関数の特性多項式が大きなメルセンヌ指数次の既約多項式と小さな多項式の積になっている場合は、小さな周期保証ベクトルを計算することが出来て、それを使って周期を保証できるのである。
MTGP 以降
じゃあ、それ以後に作られたMTGPやTinyMTでなんでその方法を使っていないのだということになるのだが、いやあ、お恥ずかしい。どうも周期保証ベクトルの計算がややこしくて、合っているという気がしなかったのである。いや、SFMTとdSFMTは松本教授がチェックしているから大丈夫なんだけど、いつまでもいちいちチェックして貰うわけにもいかんでしょ。
しかし、人間は成長するのである。最初にやったときに面倒だったので苦手意識を持ってしまったが、今の実力をもってすれば容易に倒せる相手のような気がする。ほら、最初の頃苦戦した敵もレベルアップして装備を整えれば瞬殺というあの現象ですよ。
MTToolBox に注目
というわけで、MTToolBox に新機能を追加する予定です。今後はその話を。
