用于 C++ 性能测试的随机数生成器 (2019)

随机数生成器 (RNG) 是许多计算过程的关键部分。作为生态学家，它们对于在我的模型中代表生活中的随机性特别重要。 RNG 最重要的特性是能够生成无法比随机机会更好地预测的符号或数字——这对计算机来说是非常具有挑战性的！ RNG 可以是在软件中开发的伪随机数生成器 (PRNG)，也可以是基于组件且可以是真正随机的硬件随机数生成器 (HRNG)。 PRNG 使用看似随机的确定性数字序列，但如果系统的状态完全已知，则可以重现。大多数 PRNG 由最终重复的数字序列组成，但具有如此大的周期性，以至于任何提取的数字序列都将出现随机。存在多种形式的 PRNG，但都应该涉及设置随机数种子（初始系统状态），然后运行算法以生成下一组可以转换为整数、浮点数或其他数据结构的随机位.在这里，我介绍了几个 PRNG，然后在性能方面比较了每个 PRNG 的一个非常基本的实现。我根本没有深入研究它们的统计特性——请参阅有关该主题的其他更明智的帖子！线性同余生成器 (LCG) 是最古老的 PRNG 之一。该算法由递推关系定义，其中\(a\) 是“乘数”，\(b\) 是“增量”，\(m\) 是“模数”。如果 \(b=0\) 且 \(m\) 是素数，则称为 Lehmer RNG。我们的 LCG 代码非常少，因此生成器非常快。然而，LCG 有许多缺点，主要源于相对较小的状态空间和周期性，这意味着模数应该至少是所需样本数量的三次方，以获得良好的“随机性”。这对于编程游戏或其他应用程序可能很好，但对于随机性非常重要的蒙特卡罗模拟，这通常是不可接受的。 Mersenne Twister (MT) 以梅森素数命名，通过一些统计测试来衡量时具有高度的随机性（但最近已经暴露了几个问题）。一段时间以来，它一直是许多计算领域（包括 Monte Carlo 模拟）的实际 PRNG。下面给出了 MT 的改编版本。一系列 PRNG 使用异或 (XOR)、移位 (SHI) 和位旋转 (RO) 来生成随机数。最近关于它们的统计特性存在一些争议，但它们似乎是具有出色速度的优秀全能型 PRNG 的有力竞争者。下面给出了一个版本，（令人惊讶的短）Xoroshiro128+，

另一种流行且速度非常快的算法是 SplitMix64。它是某些语言的默认设置（尽管更多语言默认使用基于 MT 的 PRNG）。同样，代码出奇地少。性能只是 PRNG 的一项重要特性，但对许多用例至关重要。我测试了一些改编自互联网上各种版本的 PRNG 的自定义实现，以及一些内置的 C++ 算法以进行比较。请注意，在基本 MT 实现和 PCG 下方生成 32 位整数而不是 64 位整数。在 2.6 GH Ivy Bridge i7 笔记本电脑处理器上对 10 9 个随机数进行了计时测试。不要把这些数字当作福音——如果速度很重要，请执行自己的测试！ Xoshiro256+ PRNG 名列前茅，紧随其后的是 SplitMix64。其余的包也不甘落后，基本实现和 MT 的速度要慢得多。与最慢的 PRNG（基本 rand 实现）的基线相比，我们看到从移动到最快的 Xoshiro256+ PRNG 的性能提高了 5 倍。所有方法都有其缺点，无论是速度还是统计“随机性”的不同缺陷。有许多在线文章（参见此处、此处和此处）讨论了特定方法的各种优点和缺点。就我个人而言，我将使用 Xoshiro256+ 算法，因为它看起来非常快，而且它的统计问题对我的工作并不重要（至少不是很明显）。否则，我可能会选择最近产生大量噪音的 PCG 方法之一，并且可能有比我在这里使用的更快的版本可用。在这里查看它们。