升级#PCG64​PCG64DXSM

在大规模并行环境中使用已被证明存在统计缺陷，这些缺陷在 numpy 1.17 的第一个版本中并不明显。大多数用户永远不会注意到这个弱点，可以安全地继续使用。我们引入了一个新的，它最终将成为未来版本中 使用的新的默认实现。解决了统计弱点，同时保留了 .PCG64 BitGeneratorPCG64PCG64DXSM BitGeneratorBitGeneratordefault_rngPCG64DXSMPCG64

这对我有影响吗？#

如果你

  1. 仅使用单个Generator实例，

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

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

  4. 明确使用BitGenerator除 之外的PCG64其他

那么这个弱点根本不会影响到你。继续。

default_rng如果您使用使用或 创建的中等数量的并行流（SeedSequence.spawn在 1000 秒内），那么观察到此弱点的机会非常小，可以忽略不计。您可以继续放心使用PCG64。

如果您使用大量并行流（数百万），并从每个流中提取大量数字，那么观察到此弱点的机会可能会变得不可忽略，尽管仍然很小。这种用例的一个例子是一个非常大的分布式强化学习问题，其中有数百万个长蒙特卡洛播放，每个播放生成数十亿个随机数抽奖。此类用例应考虑PCG64DXSM显式使用或其他现代的，BitGenerator如SFC64或Philox，但您计算的任何旧结果不太可能无效。无论如何，弱点是一种生日悖论 碰撞。也就是说，数百万个并行流中的一对单独考虑，可能无法通过一组严格的随机性统计测试。剩余的数百万个流都很好，并且在整个计算中坏对的影响很可能被大多数应用中的剩余流淹没。

技术细节＃

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

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

现在，让我们考虑增量不被限制为相同的情况。我们实行PCG64种子国家和增量；也就是说，两次调用default_rng（几乎肯定）具有不同的状态和增量。在我们的第一个版本中，我们相信拥有种子增量将提供一定程度的额外保护，状态空间和增量空间必须“接近”才能观察PractRand一对中的相关性（故障）溪流。如果这是真的，那么冲突的“瓶颈”将是内部的 128 位熵池大小SeedSequence（并且 128 位冲突属于“极其不可能”的类别）。不幸的是，事实并非如此。

LCG 的已知属性之一是不同的增量创建 不同的流，但具有已知的关系。每个 LCG 都有一个穿过所有\(2^{128}\)不同的 128 位状态。具有不同增量的两个 LCG 是相关的，因为一个可以“旋转”第一个 LCG 的轨道（将其推进我们可以根据两个增量计算的多个步长），这样两个 LCG 将始终具有相同的状态，直到一个加法常数，并且可能是位的反转。如果您随后以锁步方式迭代两个流，则状态将始终通过相同的加性常数（以及反转，如果存在）保持相关。回想一下，它PCG64是由转换函数（LCG）和输出函数构造的。预计输出函数的加扰效应将足够强以使不同的流实际上独立（即“通过测试PractRand”），除非两个增量彼此病理相关（例如1和3）。我们实现的当时标准 PCG 算法的输出函数 XSL-RRPCG64太弱，无法掩盖我们上面描述的底层 LCG 的 58 位冲突。对于任何给定的增量对，状态的“冲突”空间的大小是相同的，因此对于这个弱点，增量提供的额外清晰度并不能转化为对可PractRand检测到的统计相关性的额外保护。

幸运的是，加强输出功能能够纠正这个弱点，并且确实将不同增量提供的额外清晰度转化为针对这些低位冲突的额外保护。值得称赞的是， PCG作者在新系统诞生的漫长过程中，针对相关讨论，开发出了更强的输出功能BitGenerator。我们 NumPy 开发人员选择“保守”，使用当时经过较长时间测试的 XSL-RR 变体。 DXSM 输出函数采用强整数哈希中使用的“xorshift-multiply”结构，该结构比 XSL-RR 输出函数具有更好的雪崩特性。虽然存在一些“病态”的增量对会引发与两个流相关的“坏”加性常数，但绝大多数增量对会引发“好”加性常数，从而使仅不同的 LCG 状态流变成实际上独立的输出流。事实上，现在我们曾经提出的主张PCG64实际上是正确的PCG64DXSM：冲突是可能的，但两个流必须同时在 128 位状态空间中“接近” 并且在 127 位增量空间中“接近”，这样就比 128 位内部池中发生冲突的可能性更小SeedSequence。 DXSM 输出函数比 XSL-RR 的计算密集度更高，但 LCG 中的一些优化足以弥补大多数机器上的性能损失，因此PCG64DXSM是一个良好、安全的升级。当然，可以考虑无数种更强的输出函数，但大多数都会有更大的计算成本，而 DXSM 输出函数PractRand此时已经接受了许多 CPU 周期的测试。