Mersenne Twister

Mersenne Twisterとは?

Mersenne Twister(以下MT)は、松本眞氏 ・西村拓士氏により96年から97年に渡って開発された疑似乱数生成アルゴリズムです。非常に高速で、周期も非常に長く、究極の擬似乱数生成アルゴリズムと言えるでしょう。

MTを使う理由

良質の乱数を高速に生成する

C言語の標準ライブラリ関数である rand() は多くの場合、単純な線形合同法で実装されていますが、これは生成される乱数の質を考慮すると決して速くはありません。特に乗算が遅いプロセッサ(Intel系)では悲惨です。MTは単純な論理演算だけから乱数を生成するため高速です。線形合同法よりは若干遅い事もあるのですが、乱数の質を考えれば十分高速です。どうしても速度が要求され、乱数の質が低くても良い場合はM系列乱数を使用すべきです。こちらは、線形合同法よりも速く、質もかなり良いものです。線形合同法は質が非常に悪く、精度が要求されない分野でも、乱数とは呼べないような現象をしばしば引き起すため危険です。絶対に使用してはいけません。MTではこのような心配は全くありません。

周期が長い

周期は 2^19937-1 ということですが、これは凄まじい周期です。宇宙に存在する全粒子と同じ数のコンピュータをそろえて、宇宙誕生から現在まで、いや宇宙の終わりまで計算し続けても、MTの周期の片鱗すらも窺い知る事はないほどです。

ソースコード

MTのアセンブラ版(Pentium系プロセッサ専用)を作ったので公開します。プロセッサがMMX対応であれば、MMXを自動的に使用します。動作確認は Microsoft VC++ 6.0 で行いました。インラインアセンブラで書かれているため、他のコンパイラでは若干の修正が必要です。また、コードの一部を修正して使用する場合は注意が必要です。特にアセンブラ部にアドレスを渡しているところはポインタか配列かで命令を書き換える必要があります。問題が発生した場合はご連絡いただければできる限り対処いたします。

ベンチマーク

CPU及びクロック数 生成速度(DWORD/sec)MMX ASM C

Intel PentiumIII 700MHz

34,500,000 25,800,000 23,600,000

Intel Pentium MMX 233MHz

10,000,000 7,900,000 5,800,000

リンク