使用 PCG64 升级 PCG64DXSM#

在高度并行的环境中使用 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 中混合，这些 N 在单个流中可以观察到，这就是为什么如果您在应用程序中只使用单个流，则无需担心这一点的原因。类似地，PCG64.jumped 方法使用精心选择的步数来避免创建这些冲突。但是，一旦您开始创建“随机初始化”的并行流（通过重复调用 default_rng 或使用 SeedSequence.spawn 来创建），那么我们需要考虑需要多少个较低的位需要“碰撞”才能创建一对不良流，然后评估创建这种碰撞的概率。根据经验，如果共享状态的较低 58 位并共享增量，那么当交错时，该对流将在合理的时间内通过 PractRand 失败，在绘制几GB的数据后。按照生日悖论的标准计算，对于 58 位的碰撞，我们可以看到我们可以创建 \(2^{29}\) 个流（约 5 亿个），这时这种碰撞的概率会很高。5 亿个流相当多，每个流在统计相关性即使对严格的 PractRand 测试也变得明显之前需要提取的数据量为几GB。但这对于像分布式强化学习这样的大型应用程序来说已经近在眼前了。有理由期望即使在这些应用程序中，碰撞可能也不会对最终结果产生实际影响，因为统计问题仅限于碰撞对。

现在，让我们考虑增量不限于相同的情况。我们对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周期测试。