dSFMT jump function

dSFMT ジャンプ

dSFMT ジャンプ機能について

ジャンプ機能を使うと、dSFMTのある内部状態からNステップ後の状態を計算することが出来ます。これはdSFMTの乱数生成を2N回呼び出すのと同じことですが、 Nが大きい場合、乱数生成よりずっと速くNステップ後の状態に移ることができます。ジャンプ機能の典型的な使用法は、dSFMTによって生成される（長い）周期の中で、互いに重ならないという保証のある複数の部分列を取得することです。

ジャンプを実行するには二つのステップがあります。ジャンプ多項式の計算と内部状態の変更です。

ステップ1:ジャンプ多項式の計算

ジャンプ多項式を計算するために、計算済みの多項式を使用します。計算済みの多項式は poly.{DSFMT_MEXP}.txtファイルに保存されています。（この多項式についての説明は省略します）
make によって作られる実行可能ファイル 'calc-jump'を使って、コマンドラインからジャンプ多項式を計算することができます。使用法は以下のとおりです。

./calc-jump jump-step polynomial-file
    jump-step: a number between zero and 2^{DSFMT_MEXP}-1.
               large decimal number is allowed.
    polynomial-file: one of poly.{DSFMT_MEXP}.txt file

jump-stepは十進数で指定してください。大きな数を指定することが出来ます。 no. は、params ディレクトリにある poly.{DSFMT_MEXP}.txt ファイルを使用する時に、指定してください。
C++ の関数 'dsfmt::calc_jump' を使ってジャンプ多項式を計算することもできます。この関数は 'dSFMT-calc-jump.hpp' ファイルの中で定義されています。

ジャンプ多項式の計算にはVictor Shoup教授の NTL: A Library for doing Number Theory が必要です。
また、ジャンプ多項式の計算にはdSFMTの内部状態は必要ありませんし、計算済み多項式の格納されたファイル名以外はメルセンヌ指数にも依存しません。

ステップ2:dSFMTの内部状態をジャンプ後の状態に変更する

このステップは、dSFMTのメルセンヌ指数に依存します。ジャンプ多項式の計算に使用した計算済み多項式に対応するメルセンヌ指数を必ず使用してください。
C言語で書かれたdSFMT_jump関数がこのステップを実行します。この関数は、dSFMT-jump.hの中で宣言されています。この関数のコンパイルには、dSFMT バージョン2.2 が必要です。

ダウンロード

dSFMTJump-src-0.1.tar.gz
dSFMTJump-src-0.1.zip

インストール、コンパイル、テスト

Jump プログラムは単独ではコンパイルできません。dSFMT 2.2 のソースファイルが必要です。

NTLをインストールしていなければインストールする。
アーカイブファイルを解凍します。
出来たディレクトリ(dSFMTJump-src-xxx)の中のjumpディレクトリを dSFMTのディクレクトリにコピーします。

dSFMT-src-2.2
   +---html
   +---jump

コピーしたjumpディレクトリにcd します。
NTLのインストール時にgmp か gf2x を使用した場合は、Makefile の以下の行のどちらかのコメントを外す必要があります。

#LIBGF2X = -lgf2x
#LIBGMP = -lgmp

make を実行します

make all
make check

make check の結果 OK と表示されればテストは成功です

make check で作られた test-jump-MXXX ファイルは、-s を指定して実行するとジャンプ多項式の計算時間とジャンプの実行時間を表示します。

$ ./test-jump-M19937 -s
mexp 19937 jump 10^04 steps  calc_jump: 0.707ms
mexp 19937 jump 10^04 steps dSFMT_jump: 0.166ms
mexp 19937 jump 10^06 steps  calc_jump: 3.527ms
mexp 19937 jump 10^06 steps dSFMT_jump: 3.657ms
mexp 19937 jump 10^08 steps  calc_jump: 6.310ms
mexp 19937 jump 10^08 steps dSFMT_jump: 3.628ms
mexp 19937 jump 10^10 steps  calc_jump: 9.221ms
mexp 19937 jump 10^10 steps dSFMT_jump: 3.579ms
mexp 19937 jump 10^12 steps  calc_jump:12.175ms
mexp 19937 jump 10^12 steps dSFMT_jump: 3.638ms
mexp 19937 jump 10^14 steps  calc_jump:15.176ms
mexp 19937 jump 10^14 steps dSFMT_jump: 3.630ms
mexp 19937 jump 10^16 steps  calc_jump:18.064ms
mexp 19937 jump 10^16 steps dSFMT_jump: 3.626ms
mexp 19937 jump 10^18 steps  calc_jump:20.959ms
mexp 19937 jump 10^18 steps dSFMT_jump: 3.606ms
mexp 19937 jump 10^20 steps  calc_jump:23.884ms
mexp 19937 jump 10^20 steps dSFMT_jump: 3.600ms
mexp 19937 jump 10^22 steps  calc_jump:26.920ms
mexp 19937 jump 10^22 steps dSFMT_jump: 3.592ms

並列生成サンプル

アーカイブに同梱されている sample1.cファイルは、 dSFMT1279を使って、10²⁰ ステップのジャンプをすることによって、重なりのないことが保証された部分列を5個生成しています。5個のdSFMTが10²⁰以下の疑似乱数を生成する限り、部分列が重なることはありません。

大きめのジャンプステップを指定して、重なりのない部分列を生成することがジャンプ機能の重要な目的ですが、ジャンプ機能を使って、並列にひとつながりの疑似乱数列を生成することも出来ます。 sample2.cでは5個のdSFMT521を使用してひとつながりの疑似乱数列を生成し、ひとつのdSFMT521で順次生成した疑似乱数列と比較しています。
このサンプルでは、順次生成と比較するために、小さなジャンプステップを使っていますが、実際にひとつながりの疑似乱数列を並列生成するなら、もっと大きなジャンプステップを使用することになるはずです。

ライセンス

dSFMT-jump は dSFMT と同様に商用にも利用することができます。
詳細はLICENSE.txt を参照してください。