6

我正在使用 boost mt19937 实现进行模拟。

模拟需要可重现，这意味着存储并可能在以后重复使用 RNG 种子。我正在使用 windows 加密 api 来生成种子值，因为我需要种子的外部来源，而不是因为任何特定的随机性保证。任何模拟运行的输出都会有一个包含 RNG 种子的注释 - 所以种子需要相当短。另一方面，作为模拟分析的一部分，我将比较几次运行——但为了确保这些运行实际上是不同的，我需要使用不同的种子——所以种子需要足够长避免意外碰撞。

我已经确定 64 位播种就足够了；在大约 2^32 次运行后，发生碰撞的几率将达到 50%——这个概率足够低，以至于它引起的平均错误对我来说可以忽略不计。仅使用 32 位种子是很棘手的；在 2^16 次运行后，发生碰撞的几率已经达到 50%；这对我的口味来说有点太可能了。

不幸的是，boost 实现要么是具有完整状态向量的种子——它太长了——要么是一个 32 位无符号长的种子——这并不理想。

如何使用超过 32 位但小于完整状态向量的生成器播种？我尝试只是填充向量或重复种子来填充状态向量，但即使粗略地看一下结果也表明这会产生糟糕的结果。

4

2 回答 2

3

查看mersenne_twister 模板的 boost 来源：

  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;
    }
  }

对于 mt19937UIntType是uint32_t，w是 32。对于 64 位种子，也许您可​​以使用低 32 位计算状态的每个偶数索引 ( x)，使用高 32 位计算状态的奇数索引，使用该算法。

（虽然这是货物崇拜的建议）

于 2010-05-26T22:40:30.370 回答
3

你的假设是错误的。对于模拟，您不需要加密的强种子。事实上，使用种子 1、2、3、4 等通常是一个更好的主意。Mersenne Twister 的输出值将是不相关的，但没有人会质疑您是否精心挑选了种子以获得所需的模拟输出。

对于确实有实际需求的其他人，一种简单的方法是丢弃生成的第一个（种子>>32）值。这为您提供了大约 log2(seed>>32) 额外的状态位。但是，只有在您需要一些额外的位时，它才能有效地工作。以这种方式添加 32 位可能太慢了。

更快的算法是为好的随机生成器生成完整的状态向量。由于生成的状态向量的随机性有限，问题中提到的解决方案（重复或填充）并不是那么好。但是如果你从 的输出中填充初始状态向量mersenne_twister(seed1) ^ mersenne_twister(seed2)，这根本不是问题。

于 2010-05-27T09:33:51.640 回答