Multiple stream Mersenne Twister PRNG


[English]

プログラム
プログラム[mt_stream_f90.tar.gz] 最新へのリンク [2011/03/31]


Mersenne Twister 1系列を複数に分割して並列に(Stream)使えるようにしたものです。 MPI並列などで数千から数万の並列の乱数が必要になるのでそのために作りました。

本体部分は Fortran90/95 言語で書かれています。またデフォールトの設定では 一部外部ライブラリ(C/C++言語)を使用しています。
C/C++を使わず Fortran だけでも GF(2)[x]が扱えるようにしました[2010/03/08](要設定Makefile)。
Version 1.00 からは、NTL/GFX/C++ ライブラリとのリンクを取るために Fortran2003 で定義された ISO C Binding モジュールを使っています。このモジュールの使えるコンパイラーは私の知る限り

があります。

Mersenne Twister のパラメータは、松本眞-西村拓士両氏のオリジナルのコード(初期化改良版) [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/mt19937ar.html] のパラメータ(MT19937)が埋め込まれています。分割した部分の長さは 2^256 に 設定してあります。

分割の方法は、MT の漸化式に対応する多項式と Cayley-Hamilton の公式を使った 方法です。ただし、sliding-window 法は使わず、 Horner法で飛んだ先の状態ベクトル を計算しています。
[参考: H. Haramoto, M. Matsumoto, T. Nishimura, F. Panneton, and P. L'Ecuyer, ``Efficient Jump Ahead for F_2-Linear Random Number Generators'', GERAD Report G-2006-62. INFORMS Journal on Computing, 20, 3 (2008), 385-390.]

状態ベクトルを 2^256 だけ進めるための多項式の係数を求めるためにデフォールトでは、外部の ライブラリ、

を使用しています。これらをインストールしておく必要があります。これらのコンパイル には C,C++ 言語が必要です。
もし、C/C++/NTL/GF2X が利用できない場合は、 Fortran だけで動くように設定できます(2010/03/08)。

乱数初期化ルーチンは松本眞-西村拓士両氏のオリジナルのコード(初期化改良版MT19937)と 同じようにしており、最初の 1000 個の乱数(整数)がオリジナルのコードと同 じであることは確認しました。

並列に分割した部分(Stream)が正しくジャンプしているかは、分割部分の長さを 2^15 に設定し、元の Stream を空回しで動かした場合と、ジャンプしたものが 同じ乱数を生成することで確認しました。Stream数は 1024 個までは確認しました。

分割された stream 間の相関についてはまだ、私自身未検証です。

生成される乱数は、以下の通り。


このプログラムは無保証です。ライセンスはNew BSD Licenseに従います。


コンパイル方法
Linux, gcc/g++/gfortran or Intel compiler で開発を行った。

  1. デフォールト(C/C++/NTL/GF2Xが使える状況)では、 以下のライブラリをコンパイルしてインストールしておいてください。
    C/C++/NTL/GF2Xが使えない状況、または、Fortran だけで行いたいときは次に進んでください。
  2. プログラム(最新へのリンク)[mt_stream_f90.tar.gz]を展開する。
    コンパイラーやコンパイラーオプションに関する記述を Makefile に設定する。
    さらに Makefile に上記のライブラリへの include path, library path を設定する。
    C/C++/NTL/GF2Xが使えない状況では、Makefile に USE_NTL = no を設定する。
  3. make する。 いくつか無矛盾性のチェックが行われると思います。
  4. mt_stream.o と mt_stream.mod がこの module program の生成物です。さらに以下の生成物があります。
    NTL/GF2X を使用した場合、 が追加生成物です。
    Fortran だけで NTL/GF2X を使用しなかった場合、 が追加生成物です。
    Fortran90/95 の自分のプログラムからこの module に含まれる関数/サブルーチン を呼び出すプログラムを書いたら、コンパイル時には mt_stream.mod がコンパイラ から見えるように、リンク時には mt_stream.o と 上記の追加生成物が結合されるようにしてください。

このモジュールで使用できる関数/サブルーチンのリスト


欠点、注意点
ストリームの管理はユーザーが行なうこと。 同じ id を持つストリームを複数作ることが出来るので注意して下さい。


謝辞
Mersenne Twister のプログラムとか公開してある松本氏の Web site には 大変お世話になり、とても参考になりました。
また、ここに全ての名前を列挙できないのですが、松本氏の Web site へ 寄与した多くの方々の様々な言語による実装もとても参考になりました。 ここに感謝いたします。
プログラムを改良してくれた Michael Briggs さんに感謝します。
Tridib Sadhu さんからのバグレポートに感謝します。


コメントや改良点がありましたら、
石川健一
ishikawa[at]theo.phys.sci.hiroshima-u.ac.jp
まで。