random - 关于 Mersenne Twister 生成器的周期

Question

我读到 Mersenne Twister 生成器的周期为 2¹⁹⁹³⁷ - 1，但我很困惑为什么会这样。我看到 this implementation Mersenne Twister 算法，在第一条评论中，它清楚地表明它产生 0 到 2³² - 1 范围内的值。因此，在它产生 2³² - 1 个不同的随机数之后，它必然会回到起点(种子)，因此周期最大为 2³² - 1。

此外(请告诉我，如果我错了，请告诉我)，计算机不能保存数字 (2¹⁹⁹³⁷ - 1) ~ 4.3×10⁶⁰⁰¹，至少在单个内存块中是这样。我在这里缺少什么？

Answer 1

你的困惑源于认为输出数字和 PRNG 的内部状态必须是同一件事。

一些非常古老的 PRNG 曾经这样做过，例如线性同余生成器。在这些发生器中，电流输出被反馈到发生器中用于下一步。

然而，大多数 PRNGS，包括 Mersenne Twister，都从一个更大的状态开始工作，它更新并使用它来生成一个 32 位数字(为了这个目的，以什么顺序完成并不重要)答案)。

事实上，Mersenne Twister 确实存储了 624 乘以 32 位的值，也就是 19968 位，足以包含您想知道的很长的周期。这些值是单独处理的(作为无符号的 32 位整数)，而不是在单步计算中被视为一个巨大的数字。您从输出中获得的 32 位随机数与此状态相关，但不会自行确定下一个数字。