ブーストMersenne Twister:複数の価値でシードする方法は?
-
04-10-2019 - |
質問
シミュレーションにBoost MT19937実装を使用しています。
シミュレーションは再現可能である必要があり、それは後でRNGシードを保存して再利用する可能性を意味します。 Windows Crypto APIを使用してシード値を生成します。これは、ランダム性の特定の保証のためではなく、種子の外部ソースが必要であるためです。シミュレーション実行の出力には、RNGシードを含むメモがあります - したがって 種子はかなり短くする必要があります. 。一方、シミュレーションの分析の一環として、いくつかの実行を比較しますが、これらの実行が実際に異なることを確認するためには、異なる種子を使用する必要があります。 種子は偶発的な衝突を避けるのに十分な長さである必要があります.
私は、64ビットの播種で十分であるべきだと判断しました。衝突の可能性は、約2^32の実行後に50%に達します。その確率は十分に低く、それによって引き起こされる平均エラーは無視できます。わずか32ビットの種子を使用するのは難しいです。衝突の可能性は、2^16回の実行後、すでに50%に達します。そして、それは私の好みにはあまりにも可能性が高すぎます。
残念ながら、ブーストの実装は、完全な状態ベクトルを備えたシード(はるかに長すぎる)または32ビットの単一の署名の長いシード - 理想的ではありません。
発電機を32ビット以上でシードしますが、完全な状態ベクトルよりも少ない方法はありますか?私はベクトルをパディングするか、種子を繰り返して状態ベクターを満たしようとしましたが、結果を見ながら一見すると、結果が悪いことを示しています。
解決
あなたの仮定は間違っています。シミュレーションには、暗号化された種子は必要ありません。実際、種子を1,2,3,4などを使用することは、多くの場合、より良いアイデアです。 Mersenne Twisterの出力値は無相関になりますが、希望のシミュレーション出力を取得するために種子を選択したかどうかは誰にも疑問を呈しません。
本当のニーズを持っている他の人々にとって、1つの簡単な方法は、生成された最初の(シード>> 32)値を破棄することです。これにより、log2(Seed >> 32)の追加の状態について説明します。ただし、いくつかの追加ビットが必要な場合にのみ効率的に機能します。この方法で32ビットを追加すると、おそらく遅すぎるでしょう。
より高速なアルゴリズムが次のとおりです 生む 良好なランダムジェネレーターの完全な状態ベクトル。質問(繰り返しまたはパディング)に記載されているソリューションは、結果の状態ベクトルのランダム性が限られているため、あまり良くありません。ただし、の出力から初期状態ベクトルを埋める場合 mersenne_twister(seed1) ^ mersenne_twister(seed2)
, 、これはまったく問題ではありません。
他のヒント
見つめている Mersenne_twisterテンプレートのソースをブーストします:
void seed(UIntType value)
{
// New seeding algorithm from
// http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
// In the previous versions, MSBs of the seed affected only MSBs of the
// state x[].
const UIntType mask = ~0u;
x[0] = value & mask;
for (i = 1; i < n; i++) {
// See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
}
}
MT19937用 UIntType
は uint32_t
, w
64ビットシードの場合、下部32ビットを使用して、状態のすべてのインデックスを計算できます(x
)そして、そのアルゴリズムを使用して、状態の奇数インデックスを計算するための高い32ビット。
(これは貨物カルトの提案です)