gpt4 book ai didi

random - 测试 PRNG 的质量

转载 作者:行者123 更新时间:2023-12-04 13:24:17 25 4
gpt4 key购买 nike

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

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

编辑 1:之前没注意,但是有一个类似的帖子:How to test random numbers?

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

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

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

    最佳答案

    有几个可用的统计测试套件。我编写、复制和以其他方式收集了 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 都有接口(interface)问题。
  • 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 都作为不推荐的 PRNG 包含在 PractRand 中。

    关于random - 测试 PRNG 的质量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9780267/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com