7

我正在玩 PRNG（比如 Mersenne Twister 和rand()stdlib 的功能），我想要一个很好的测试来帮助我确定 PRNG 产生的随机数据的质量。我已经使用 PRNG 生成的随机数计算了 Pi 的值，我发现rand()和 Mersenne Twister 非常接近以提供区别（我需要在小数点后 10 位后仔细检查吗？）。

我对蒙特卡洛模拟不太了解。请让我知道一些算法/应用程序（可能是一些简单但可以提供良好推论的东西），这将有助于我在质量方面区分它们。

编辑1：我之前没有注意到，但是有一个类似的线程：如何测试随机数？

编辑 2：如其中一条评论所述，我无法解释 NIST 的结果。我从random.org得到了视觉解释模式（如果有的话）的想法，并且因为它的简单性而遵循它。如果有人可以评论我的测试过程，我会很高兴：

  1. 使用 rand() 和 MT1997 从 [0,1] 生成 N 个随机数
  2. 如果则为(round(genrand_real1() / rand_0_1()))红色像素，否则为黑色

据我了解，这不是一个非常精确的解决方案，但如果这提供了一个合理的估计，那么我现在可以接受这个。

4

3 回答 3

11

有几个可用的统计测试套件。我编写、复制和以其他方式收集了 120 个 PRNG，并使用各种测试套件对每个 PRNG 进行了测试，每个测试套件每个 PRNG 需要 4 小时：

  • PractRand（标准，1 TB）在 78 个 PRNG 中发现了偏差
  • TestU01 (BigCrush) 在 50 个 PRNG 中发现了偏差
  • RaBiGeTe（扩展，512 兆位，x1）在 40 个 PRNG 中发现了偏差
  • Dieharder（自定义命令行选项）在 25 个 PRNG 中发现了偏差
  • Dieharder（-a 命令行选项）在 13 个 PRNG 中发现偏差
  • NIST STS（默认，64 兆位 x128）在 11 个 PRNG 中发现偏差

其中有多少是其他测试套件都错过的 PRNG？

  • PractRand（标准，1 TB）在各种类别中发现了 22 个独特的偏见。
  • RaBiGeTe（扩展，512 兆位，x1）发现了 5 个独特的偏差，都在 LCG 和组合 LCG 中。
  • TestU01 BigCrush 发现了 2 个独特的偏差，都是在小的混乱 PRNG 中。
    没有其他测试套件发现任何独特的偏差。

简而言之，只有 PractRand、TestU01 和可能的 RaBiGeTe 值得使用。

全面披露：我写了 PractRand，因此 PRNG 集或任何其他非定性度量都可能偏向于它。

其他优点：

  • 在我看来，PractRand 和 TestU01 往往是最容易解释输出的。
  • 我认为 PractRand 和 Dieharder 往往是最容易通过命令行界面进行自动化测试的。
  • PractRand 和 RaBiGeTe 是唯一支持多线程测试的。

其他缺点：

  • 与其他测试套件相比，PractRand 需要更多的输入来进行测试——如果您的 RNG 速度非常慢或生成的数据量受到限制，这可能会成为问题。
  • RaBiGeTe 和 NIST STS 都有接口问题。
  • Dieharder 和 NIST STS 都存在误报问题。
  • 在我看来，NIST STS 的界面最差。
  • 我无法让 Dieharder 在 Windows 上编译。我设法让 TestU01 在 Windows 上编译，但它需要一些工作。
  • RaBiGeTe 的最新版本是封闭源代码且仅限 Windows。

测试的一组 PRNG： PRNG 集包括 1 个大型 GFSR、1 个大型 LFSR、4 个 xorshift 类型 PRNG、2 个 xorwow 类型 PRNG、3 个其他不完全 LFSR PRNG。它包括 10 个简单的 2 次幂模数 LCG（丢弃低位以达到可接受的质量水平）、10 个 2 次幂模数 not-quite-LCG，以及 9 个主要基于 LCG 和 not-quite-LCG 的组合生成器. 它包括 19 个降低强度的 CSPRNG 版本，以及一个全强度 CSPRNG。其中，14 个基于间接/动态 s-box（例如 RC4、ISAAC），4 个是 ChaCha/Salsa 参数化，其余 2 个是 Trivium 变体。它包括 11 个广泛分类为 LFib 类型或类似类型的 PRNG，不包括 LFSR/GFSR。其余的（大约 35 个）是小状态混沌 PRNG，其中 10 个使用乘法，其他的仅限于算术和按位逻辑。

编辑：gjrand中还有一个测试集，它非常晦涩且有点奇怪，但实际上做得非常好。

此外，所有测试的 PRNG 都作为不推荐的 PRNG 包含在 PractRand 中。

于 2014-11-26T23:13:44.387 回答
4

有两个用于测试随机数的标准测试套件。

  1. NIST测试套件。他们在 C 中有一个实现。
  2. 死硬测试套件（由 George Marsaglia 开发）。这些测试有一个C 库实现。

Dieharder 库有一个 R 接口，称为RDieHarder。该库为 NIST 和 Diehard 测试套件提供了一个接口。

于 2012-03-20T10:34:35.193 回答
0

你最好看看Knuth 系列的第 2 卷。

如需更短的阅读，请查看数字食谱的相应章节。

如果您只对 MC 模拟的一种基线感兴趣——最好避免使用线性同余生成器，Mersenne Twister在绝大多数情况下都足够好。

于 2012-03-20T10:27:36.667 回答