帰ってきた「しっぽのさきっちょ」

しっぽのさきっちょ: 2016-03-17 付

Mersenne Twister に関する覚え書き

no extension

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

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

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

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

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

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

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

ブックマーク


  1. $2^{19937}-1$ はメルセンヌ素数で Mersenne Twister の名前の由来になっている。 Mersenne Twister では周期サイズごとに複数の実装があるが, $2^{19937}-1$ がポピュラーな実装として広く使われているようだ。 [return]
  2. Mersenne Twister は「予測可能」であるため暗号技術など高いセキュリティが要求される場合には使えない。暗号技術における乱数生成器の要件については RFC 4086IPA による日本語訳)などが参考になる。なお Mersenne Twister を応用した CryptMT というのはある。 [return]
  3. MIT ライセンスでの利用も可能らしい。 [return]