梅森·特维斯特--有没有办法跳到一个特定的状态？

Question

我对这个问题的合适论坛有点不确定。这是理论上的比较。sci/数学和编程。

我用Mersenne-Twister生成伪随机数。现在，从给定的种子开始，我想跳到序列中的n个数。

我已经看到了这一点：http://www-personal.umich.edu/~wagnerr/MersenneTwister.html，有一个方案可以如下所示：

假设，我只需要特定种子的完全随机序列中的第一个N个数。

我将序列分成p个子序列，遍历所有的N个数，并在每个子序列的开头保存随机数生成器的状态向量。

现在，为了达到n个数，我将看到n落在k子序列中，我将加载这个子序列的状态向量，并生成m个连续随机数，其中k子序列中的m个数与完全序列中的n个数相同(n=m+ (k-1) * N/p )。

但是状态向量是624x4字节长！我想知道，在mersenne-twister生成的序列中，是否有可能跳转到任意元素。

Answer 1

是的，这是可能的！这叫跳跃式前进。

你可以在MT作者的主页上找到用Mersenne做这件事的所有细节。现有代码以及解释该算法的科学出版物：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/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

我认为你想要的是违反密码安全随机数生成器的定义，所以不幸的是，我认为这是不可能的。