Mersenne Twister に関する覚え書き

「ズンドコキヨシ」で興味が出たので Mersenne Twister について調べている。 適宜追加予定。

Mersenne Twister とは松本眞・西村拓士両氏によって1996年に発表された擬似乱数生成アルゴリズムである。 他の擬似乱数生成アルゴリズムと比べて以下の特徴があるそうだ。 （「Mersenne Twister とは?」より）

• 従来の様々な生成法の欠点を考慮して設計されています。
• 従来にない長周期, 高次元均等分布を持ちます。（周期が $2^{19937}-1$ で¹、623次元超立方体の中に 均等に分布することが証明されています。）
• 生成速度がかなり速い。（処理系にもよりますが、パイプライン処理やキャッシュメモリ のあるシステムでは、Cの標準ライブラリの rand() より高速なこと もあります。なお、開発当時には cokus 版は rand() より4倍程度高速でしたが、その後 ANSI-C の rand() が LCG 法から lagged-fibonacci に 変更されたこともあり、2002年現在 rand と MT の速度差はあまりありません。）
• メモリ効率が良い。（32ビット以上のマシン用に設計された mt19937.c は、 624ワードのワーキングメモリを消費するだけです。 1ワードは32ビット長とします。

Mersenne Twister が主に使われるのは科学シミュレーション（最近流行りのモンテカルロ法とか）だが，比較的メモリ効率がよいためゲームなどでも使われるらしい²。 また JIS Z 9031 の附属書 B にも Mersenne Twister のコードが掲載されている。 改良版の SFMT (SIMD-oriented Fast Mersenne Twister) や $2^{127}-1$ 周期の軽量版 TinyMT などがある。

オリジナルのコードは GitHub で公開されている。

• MersenneTwister-Lab
  • SFMT
  • dSFMT （倍精度浮動小数点擬似乱数を直接生成できる）
  • TinyMT

主に C 言語で記述されており BSD ライセンスで提供されている³。 また C++, PHP, Python, Ruby などの言語では標準で組み込まれている。

• std::mersenne_twister_engine - cppreference.com
• PHP: mt_srand - Manual
• 9.6. random — Generate pseudo-random numbers — Python 3.3.6 documentation
  • 9.6. random — Generate pseudo-random numbers — Python 2.7.11 documentation
• Class: Random (Ruby 2.3.0)

これら以外では Java や Go などによる実装がある。

• TinyMT Java Implementation (Japanese) （オリジナル）
• Sean Luke : Code に Mersenne Twister の Java 実装が紹介されている
• seehuhn/mt19937: An implementation of Takuji Nishimura’s and Makoto Matsumoto’s Mersenne Twister pseudo random number generator in Go. （GPL ライセンスなので取り扱いに注意）

ブックマーク

• 有限体の擬似乱数への応用
• 間違いだらけの疑似乱数選び
• 良い乱数・悪い乱数
• Multiple stream Mersenne Twister PRNG