增强梅森旋转器：如何播种多个值？

StackOverflow https://stackoverflow.com/questions/2914986

  •  04-10-2019
  •  | 
  •  

题

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

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

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

不幸的是，boost 实现要么使用完整的状态向量（这太长了），要么使用单个 32 位无符号长整型（这并不理想）。

如何为生成器提供超过 32 位但小于完整状态向量的种子？我尝试仅填充向量或重复种子来填充状态向量，但即使粗略地浏览一下结果也会发现，这会产生很差的结果。

有帮助吗？

解决方案

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

对于确实有真正需要的其他人来说，一种简单的方法是丢弃产生的第一个（种子>> 32）值。这为您提供了log2（种子>> 32）的额外状态。但是，仅当您需要一些额外的位时，它才有效。以这种方式添加32位可能太慢了。

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

其他提示

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

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

（尽管这是货物崇拜的建议）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top