测试PRNG的质量

Question

我正在玩PRNG(比如Mersenne和stdlib的rand()函数)，我想要一个好的测试来帮助我确定PRNG产生的随机数据的质量。我用PRNG产生的随机数计算了Pi的值，我发现rand()和Mersenne非常接近于提供一个区分(我需要在小数点后仔细检查吗？)

我对Monte模拟不太了解；请让我知道一些算法/应用程序(可能是一些简单但可以提供良好推论的算法/应用程序)，这些算法/应用程序可以帮助我在质量上区分它们。

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

编辑2:我无法解释NIST的结果，正如注释中提到的那样。我从random.org中获得了可视化解释模式(如果有的话)的想法，并且由于它的简单性，我一直在遵循它。如果有人能对我的测试过程发表评论，我将非常高兴：

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

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

Answer 1

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

1. NIST测试套件。他们有一个在C.
2. 顽固性试验套房 (由George开发)。这些测试有一个C库实现。

Dieharder库有一个名为RDieHarder的R接口。这个库为NIST和死硬测试套件提供了一个接口。

Answer 2

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

• PractRand (标准，1TB)在78个PRNG中发现了偏差
• TestU01 (BigCrush)在50个PRNG中发现了偏差
• RaBiGeTe (Extended512兆比特，x1)在40个PRNG中发现了偏差
• 迪哈德 (自定义命令行选项)在25个PRNG中发现了偏差
• 迪哈德 (-a命令行选项)在13个PRNG中发现了偏差
• NIST STS (默认，64兆比特x128)在11个PRNG中发现了偏差

有多少是在PRNG中，而其他测试套件都漏掉了？

• PractRand (标准，1TB)发现22个独特的偏差，种类繁多。
• RaBiGeTe (Extended512兆比特，x1)发现了5种独特的偏差，全部存在于LCG和组合LCG中。
• TestU01 BigCrush发现了两个独特的偏差，它们都存在于小的混沌PRNG中。 没有其他测试套件发现任何独特的偏见。

简而言之，只有、TestU01和RaBiGeTe值得使用.

完全披露:我写了PractRand，所以无论是PRNG还是任何其他非定性的措施都可能对它有利。

杂项优势：

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

杂项缺点：

• 与其他测试套件相比，PractRand需要更多的输入--如果您的RNG非常慢，或者在生成的数据量上受到其他限制，这可能是一个问题。
• RaBiGeTe和NIST都存在接口问题。
• Dieharder和NIST STS都存在假阳性问题。
• 在我看来，NIST STS的界面最差。
• 我无法在Windows上编译Dieharder。我设法让TestU01在windows上编译，但这需要一些工作。
• RaBiGeTe的最新版本是封闭源代码和windows专用的.

测试组：：PRNG组包括1个大GFSR、1个大LFSR、4个xorshift型PRNGs、2个xorwow型PRNGs、3个其他不完全LFSR。它包括10个简单的功率2模数LCGs (它丢弃低比特以达到可接受的质量水平)，10个功率的2模数不完全LCG，和9个组合发电机主要围绕LCG和不完全LCG。它包括19个减少的强度版本的CSPRNG，加上一个完整的强度CSPRNG。其中14种是基于间接/动态s-盒(如RC4、艾萨克)，4种是ChaCha/Salsa参数化，其余2种是Trivium变体。它包括11个广泛分类为LFib型或类似的PRNGs，不包括LFSRs/GFSR。其余(约35)为小状态混沌PRNG，其中10个采用乘法，其余仅限于算术逻辑和位逻辑。

编辑：还有吉兰德中的测试集，它非常晦涩，有点奇怪，但实际上做得非常好。

此外，在PractRand中，所有测试的PRNG都被列为不推荐的PRNG.

Answer 3

你最好调查一下Knuth系列第2卷。

要阅读较短的内容，请查阅相应的数字规则章节。

如果你只对MC模拟的基线感兴趣--线性同余发生器是最好的避免，Mersenne Twister在绝大多数情况下是足够好的。