TinyMT Jump Function

READ ME FIRST

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

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

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

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

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

使用方法

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

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

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

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

3. コピーしたjumpディレクトリにcd します。
4. make all でテスト用のプログラムがコンパイルされます。
5. ./jump_test32 d8524022ed8dff4a8dcc50c798faba43 8f7011ee fc78ff1f 3793fdff 1298
6. 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);

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

この関数は計算済みのジャンプ多項式を使って、tinymt32の内部状態をジャンプさせます。 ジャンプ多項式の計算よりもこの関数によるジャンプの方が速いので、多項式を何度も 計算するよりこの関数を複数回実行した方が速くなります。

tiny は状態をjumpさせるtinymt32_t 型の構造体です。 tiny は初期化をしてある必要があります。jump 後の状態で上書きされます。

jump_polyはcalculate_jump_polynomial関数で計算したジャンプ多項式です。 ここで使用するtinyの特性多項式を使って計算したジャンプ多項式でなければなりません。

サンプルプログラム

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