使用 PCG64DXSM 升级 PCG64#

在海量并行上下文中使用 PCG64 BitGenerator 已显示出统计弱点，这些弱点在 NumPy 1.17 首次发布时并不明显。大多数用户永远不会观察到此弱点，可以安全地继续使用 PCG64。我们引入了一个新的 PCG64DXSM BitGenerator，它最终将在未来的版本中成为 default_rng 使用的新默认 BitGenerator 实现。PCG64DXSM 解决了统计弱点，同时保留了 PCG64 的性能和特性。

这会影响我吗？#

如果您

  1. 只使用一个 Generator 实例，

  2. 只使用 RandomState 或 numpy.random 中的函数，

  3. 只使用 PCG64.jumped 方法生成并行流，

  4. 明确使用 BitGenerator（非 PCG64），

那么这个弱点完全不会影响您。请继续使用。

如果您使用由 default_rng 或 SeedSequence.spawn 创建的适量（数千个）并行流，那么观察到此弱点的可能性小到可以忽略不计。您可以放心地继续使用 PCG64。

如果您使用非常大量的（数百万个）并行流，并从每个流中抽取大量数字，那么观察到此弱点的可能性可能变得不可忽略，尽管仍然很小。这种用例的一个例子是，一个非常大的分布式强化学习问题，其中有数百万次长时间的蒙特卡洛模拟，每次模拟生成数十亿个随机数。此类用例应考虑明确使用 PCG64DXSM 或其他现代 BitGenerator，例如 SFC64 或 Philox，但您之前计算的任何旧结果不太可能无效。无论如何，这个弱点是一种 生日悖论 式的碰撞。也就是说，数百万个并行流中，只有一对流，当它们被一起考虑时，可能会未能通过一组严格的随机性统计测试。其余的数百万个流都将是完全正常的，而且在大多数应用程序中，坏对流在整个计算中的影响很可能被其余流所淹没。

技术细节#

像许多 PRNG 算法一样，PCG64 由一个转换函数和一个输出函数构成。转换函数推进 128 位状态，输出函数将 128 位状态混合成 64 位整数输出。PCG 系列 PRNG 的指导设计原则之一是平衡转换函数和输出函数之间的计算成本（和伪随机性强度）。转换函数是一个 128 位线性同余生成器 (LCG)，它包括将 128 位状态乘以一个固定的乘法常数，然后在一个 128 位模运算中添加一个用户选择的增量。LCG 是经过充分分析的 PRNG，具有已知的弱点，尽管 128 位 LCG 足够大，即使只使用简单的输出函数也能通过严格的统计测试。PCG64 的输出函数旨在通过对位进行“刚好足够”的混淆来弥补一些已知弱点，从而有助于统计特性，而不会增加过多的计算成本。

这些已知弱点之一是，将 LCG 的状态推进步数是 2 的幂 (bg.advance(2**N)) 时，较低的 N 位将与刚刚离开的状态相同。对于按顺序抽取的单个流，这几乎没有影响。剩余的 \(128-N\) 位提供了足够的伪随机性，在任何实际的 N 值下，这些位都将被混合到单个流中，这就是为什么如果您在应用程序中只使用单个流，则无需担心这个问题。类似地，PCG64.jumped 方法使用精心选择的步数来避免创建这些碰撞。然而，一旦您开始创建“随机初始化”的并行流，无论是通过重复调用 default_rng 使用操作系统熵，还是使用 SeedSequence.spawn，那么我们就需要考虑有多少低位需要“碰撞”才能创建一对不良流，然后评估创建这种碰撞的概率。根据经验，已经确定如果共享状态的低 58 位并共享一个增量，那么这对流在交错时，在抽取几 GB 数据后，将在合理的时间内未能通过 PractRand 测试。根据 58 位碰撞的标准生日悖论计算，我们可以看到我们可以创建 \(2^{29}\) 个流，大约是 5 亿个，此时发生这种碰撞的概率变得很高。5 亿个流的数量非常高，每个流需要抽取的数据量在达到千兆字节级别时，统计相关性才会在即使是严格的 PractRand 测试中变得明显。但对于像分布式强化学习这样的大型应用程序来说，这已在预料之中。有理由预期，即使在这些应用程序中，碰撞可能也不会对总结果产生实际影响，因为统计问题仅限于碰撞对。

现在，让我们考虑增量不被限制为相同的情况。我们实现的 PCG64 同时播种状态和增量；也就是说，对 default_rng 的两次调用（几乎可以肯定）具有不同的状态和增量。在我们首次发布时，我们相信播种增量会提供一定程度的额外保护，即为了观察一对流中的相关性（PractRand 失败），必须在状态空间和增量空间中都“接近”。如果这是真的，那么碰撞的“瓶颈”将是 SeedSequence 内部的 128 位熵池大小（而 128 位碰撞属于“荒谬地不可能”的类别）。不幸的是，事实并非如此。

LCG 的一个已知特性是，不同的增量会创建不同的流，但它们之间存在已知的关系。每个 LCG 都有一个遍历所有 \(2^{128}\) 个不同 128 位状态的轨道。两个具有不同增量的 LCG 之间的关系是，一个 LCG 的轨道可以通过“旋转”（将其推进我们从两个增量中可以计算出的步数）来使两个 LCG 始终具有相同的状态，直至一个加性常数和（如果存在）位的反转。如果您然后同步迭代这两个流，那么它们的状态将始终通过相同的加性常数（和反转，如果存在）保持相关。回想一下，PCG64 是由转换函数（LCG）和输出函数共同构建的。我们曾期望输出函数的混淆效果足够强大，足以使这些不同的流实际上是独立的（即“通过 PractRand 测试”），除非两个增量之间存在病态关系（例如 1 和 3）。然而，事实证明，我们在 PCG64 中实现的当时标准 PCG 算法的 XSL-RR 输出函数太弱，无法弥补我们上面描述的底层 LCG 的 58 位碰撞。对于任何给定的增量对，状态的“碰撞”空间大小是相同的，因此对于这个弱点，增量提供的额外差异性并不能转化为额外的保护，以抵御 PractRand 可以检测到的统计相关性。

幸运的是，加强输出函数能够纠正这一弱点，并且确实将不同增量提供的额外差异性转化为对这些低位碰撞的额外保护。值得称赞的是，PCG 作者在新 BitGenerator 系统漫长诞生期间，针对相关讨论开发了更强的输出函数。我们 NumPy 开发者选择“保守”地使用当时经过更长时间测试的 XSL-RR 变体。DXSM 输出函数采用了用于强整数哈希的“异或移位-乘法”构造，其雪崩特性比 XSL-RR 输出函数要好得多。虽然存在导致“不良”加性常数（与两个流相关联）的“病态”增量对，但绝大多数增量对都会产生“良好”的加性常数，使仅是不同的 LCG 状态流转化为实际独立的输出流。事实上，我们曾经对 PCG64 做出的断言现在对 PCG64DXSM 来说是真实的：碰撞是可能的，但两个流必须同时在 128 位状态空间中“接近”并且在 127 位增量空间中“接近”，因此这比 128 位内部 SeedSequence 池中发生碰撞的微不足道的可能性更小。DXSM 输出函数的计算密集度高于 XSL-RR，但 LCG 中的一些优化弥补了在大多数机器上的性能损失，因此 PCG64DXSM 是一个良好、安全的升级。当然，还有无限数量的更强的输出函数可以考虑，但大多数都将具有更高的计算成本，而 DXSM 输出函数目前已通过 PractRand 进行了大量的 CPU 周期测试。