Mersenne Twister-特定の状態にジャンプする方法はありますか？

Question

私はこの質問に適したフォーラムについて少し確信が持てません。理論的なコンプの間にあります。 Sci./mathとプログラミング。

Mersenne-Twisterを使用して、擬似乱数を生成します。さて、特定の種子から始めて、シーケンスのn番目の数値にジャンプしたいと思います。

私はこれを見ました： http://www-personal.umich.edu/~wagnerr/mersennetwister.html, 、および1つのスキームは次のとおりです。

想定してください、私は最初のものだけが必要です n 特定の種子からの完全なランダムシーケンスの数字 s.
シーケンスをに分割します p サブシーケンス、すべてのn番号を行進し、各サブシーケンスの開始時に乱数ジェネレーターの状態ベクトルを保存します。
今到達する n- 数字、私はそれを見るでしょう n に落ちる k-ths shindecenceと私はこのサブセクセンスのために状態ベクトルをロードし、生成します m k番目のサブシーケンスのm番目の数が完全なシーケンス（n = m +（k-1） * n/p）のn番目の数と同じ連続乱数があります。

しかし、状態ベクトルの長さは624 x 4バイトです！ Mersenne-Twisterが生成したシーケンスの任意の要素にジャンプすることが実際に可能かどうか疑問に思います。

Answer 1

はい、それは可能です！それは呼ばれています 一足先.

MTの著者のホームページで、Mersenne Twisterでこれを行うためのすべての詳細を見つけることができます。コードは、アルゴリズムを説明する科学出版物と同様に利用可能です。

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/jump/index.html

Answer 2

今日、これを使用する方法があります 破棄. 。複雑さは、同等の進歩の数で線形です。

作業例：

  std::mt19937 engine(0);
  std::uniform_int_distribution<int> dis(0, 9);
  auto generator = std::bind(std::ref(dis), std::ref(engine));

  qDebug() << "First sequence: ";
  for (int i = 0; i < 20; i++) {
    qDebug() << "Random value: " << generator();
  }

  engine.seed(0); // reset
  engine.discard(15); // discard the first 15 numbers from the first sequence
  qDebug() << "Last five numbers from first sequence: ";
  for (int i = 0; i < 5; i++) {
    qDebug() << "Random value: " << generator();
  }

Answer 3

Mersenne Twisterは、f上の（かなり大きな）マトリックスとして表現できます₂ （2つの要素0と1を含むフィールド）。次の状態への移行は、このマトリックスによる乗算です。

ストリーム内の任意の位置にジャンプするには、繰り返し二乗してこのマトリックスの対応するパワーを計算し、初期状態を掛けることができます。

Answer 4

あなたが求めているのは、暗号化的に安全な乱数ジェネレーターの定義に反すると思うので、残念ながら私はそれが不可能だとは思いません。