测试PRNG的质量

Question

我正在玩PRNG(如Mersenne Twister和rand()stdlib的功能),我想要一个很好的测试,这将有助于我确定PRNG产生的随机数据的质量.我使用PRNG生成的随机数计算了Pi的值,我发现rand()和Mersenne Twister非常接近提供区别(我需要在10个小数点后仔细检查吗？).

我对蒙特卡罗模拟没有太多了解; 请让我知道一些算法/应用程序(可能是一些简单但可以提供良好推论的东西),这将有助于我在质量方面区分它们.

---

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

编辑2:我无法解释NIST的结果,如其中一条评论中所述.我从random.org那里得到了从视觉上解释模式(如果有的话)的想法,因为它很简单.如果有人可以评论我的测试过程,我会很高兴:

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

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

Answer 1

有几个统计测试套件可用.我编写,复制并以其他方式收集了120个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在小型混乱PRNG中发现了2个独特的偏差.
  没有其他测试套件发现任何独特的偏见.

简而言之,只有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次方模数不完全LCG,以及9个主要基于LCG和非LCG的组合发生器.它包括19种强度降低的CSPRNG,以及一种全强度CSPRNG.其中,14个基于间接/动态s-box(例如RC4,ISAAC),4个是ChaCha/Salsa参数化,其余2个是Trivium变体.它包括11个广泛分类为LFib类型或类似的PRNG,不包括LFSR/GFSR.其余的(约35个)是小状态混沌PRNG,其中10个使用乘法而其他仅限于算术和按位逻辑.

编辑:在gjrand中也有测试集,这是非常模糊和有点奇怪,但实际上非常好.

此外,所有测试的PRNG都包含在PractRand中作为非推荐的PRNG.

Answer 2

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

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

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