TinyMT Jump Function

Jump 関数は疑似乱数生成器 TinyMT の内部状態をN個先にジャンプさせます。 Nが大きい場合、このジャンプはN個の疑似乱数を生成するよりもずっと速く実行出来ます。 Jump 関数を使用することによって、疑似乱数の出力の中から重複しない部分列を得ることができます。

Jump 関数はC言語で書かれていて、標準ライブラリ以外のライブラリを使用していません。ただし、c99 の stdint.h と inttypes.h を使用しています。

TinyMTを用いて疑似乱数列を並列に生成する方法の比較

パラメータを一つ使用し、seedを変えることによって複数の疑似乱数列を得る方法。この方法によって得られた数列は一つの疑似乱数列の部分数列ですが、それぞれの部分数列が他の部分数列とどれだけ離れているかを知ることは難しい。最悪の場合、疑似乱数列が重複する可能性があります。ただし、重複する可能性は通常無視出来るほど小さいと考えられます。一方、同一のパラメータを使用することから、マルチスレッドのようなメモリ共有並列モデルでは、パラメータを定数にすることができます。
パラメータを一つ使用し、jumpによって、複数の疑似乱数列を得る方法。この方法によって得られる数列も一つの疑似乱数列の部分数列ですが、それがお互いにどのくらい離れているかは、分かっています。つまり、jump で指定した値だけ離れています。マルチスレッドなどのメモリ共有並列モデルでは、パラメータを定数にすることができます。
個々の疑似乱数列に異なるパラメータを使用して、複数の疑似乱数列を得る方法。三つの方法の中で、各疑似乱数列の独立性が最も高いと考えられます。パラメータを定数にすることが出来ないのでメモリ消費量が増えます。

このjump関数は二番目の方法を提供します。ただし、メモリを節約するプログラムは用意していないので、メモリを節約したければ、ユーザー自身で構造体を書き換え、パラメータを定数として定義する必要があります。

Download

TinyMTJump-src-1.2.tar.gz ヘッダファイルをC++からのincludeに対応しました。
TinyMTJump-src-1.2.zip ヘッダファイルをC++からのincludeに対応しました。
TinyMTJump-src-1.1.tar.gz ドキュメントとサンプルを少し変えました。
TinyMTJump-src-1.1.zip ドキュメントとサンプルを少し変えました。
TinyMTJump-src-1.0.tar.gz
TinyMTJump-src-1.0.zip

使用方法

テストプログラムのコンパイル

Jump プログラムは単独ではコンパイルできません。TinyMT のソースファイルが必要です。また、実行にはTinyMTDCの出力パラメータが必要です。

アーカイブファイルを解凍します。
出来たディレクトリ(TinyMTJump-src-xxx)の中のjumpディレクトリを TinyMTのディクレクトリにコピーします。

TinyMT-src-xxx
   +---dc
   +---tinymt
   +---jump

コピーしたjumpディレクトリにcd します。
make all でテスト用のプログラムがコンパイルされます。
./jump_test32 d8524022ed8dff4a8dcc50c798faba43 8f7011ee fc78ff1f 3793fdff 1298
OK が表示されていることと、NGが表示されていないことを確認します。

関数の説明

void tinymt32_jump(tinymt32c_t *tiny,
                   uint64_t lower_step,
                   uint64_t upper_step,
                   const char * poly_str);

この関数はtinymt32の内部状態をlower_step と upper_step で表される 0から2¹²⁸-1の範囲内の任意のステップ先にジャンプさせます。: tiny は状態をjumpさせるtinymt32_t 型の構造体です。 tiny は初期化をしてある必要があります。jump 後の状態で上書きされます。; lower_step と upper_step は何個先の状態にjumpするかを示します。; poly_str は tinymt32dc の出力のパラメータセットの中のcharacteristic カラムを文字列として渡します。

void calculate_jump_polynomial(f2_polynomial *jump_poly,
                               uint64_t lower_step,
                               uint64_t upper_step,
                               const char * poly_str);

Ver. 1.1 より
この関数は、特性多項式とlower_step, upper_stepから対応するN ステップジャンプ多項式を計算します。ここで求めたNステップジャンプ多項式を用いて、次のtinymt32_jump_by_polynomial関数により高速にNステップジャンプが実行できます。特性多項式が同一のtinyMTに対して、Nステップのジャンプを複数回計算する場合には、ここで求めたNステップジャンプ多項式をそのまま何度でも使えます。 この関数の実行にはやや時間がかかります(とはいえ、1マイクロ秒未満で計算されます)。ジャンプのステップ数が同じならば、ジャンプ多項式を一度求めたら、それを複数回使用するとよいでしょう。 ただし、特性多項式が異なる場合は、ジャンプ多項式を計算しなおす必要があります。: jump_poly には計算結果のジャンプ多項式が入ります。; lower_step と upper_step は何個先の状態にjumpするかを示します。; poly_str には tinymt32dc の出力のパラメータセットの中のcharacteristic カラムを文字列として渡します。

void tinymt32_jump_by_polynomial(tinymt32_t *tiny,
                                 f2_polynomial * jump_poly);

Ver. 1.1 より
この関数は計算済みのジャンプ多項式を使って、tinymt32の内部状態をジャンプさせます。ジャンプ多項式の計算よりもこの関数によるジャンプの方が100倍以上速いので、同じステップ数のジャンプを複数回実行する場合には、ジャンプ多項式を一度求めて保存し、この関数を複数回実行した方が速くなります。: tiny は状態をjumpさせるtinymt32_t 型の構造体です。 tiny は初期化をしてある必要があります。jump 後の状態で上書きされます。; jump_polyはcalculate_jump_polynomial関数で計算したジャンプ多項式です。ここで使用するtinyの特性多項式を使って計算したジャンプ多項式でなければなりません。

サンプルプログラム

サンプルプログラムsample.cを挙げておきます。

Back to TintMT Home Page