最佳伪随机数发生器

Question

截至今天哪个是最好的伪随机数发生器？最好的我是指那个 -

1. 通过所有统计测试
2. 即使在非常高的尺寸下也表现良好
3. 有一个非常大的时期

我能想到MT.有没有比MT好的PRNG？MT的哪种变体最好？

Answer 1

只是一个快速的更新,因为答案显示他们的年龄:今天Mersenne Twister不再被认为是最先进的技术(有点臃肿,可预测只有624个值,播种速度慢,播种可能不好,......).

普通PRNG

对于正常应用,需要考虑良好的统计特性和速度

• 奥尼尔的PCG家族,和
• Vigna的xoroshiro家族,比如xoroshiro128 +(不是日本名字顺便说一句,但是"X-或,旋转,移位,旋转").

密码安全PRNG(CSPRNG)

对于非可预测性很重要的加密应用程序,请考虑加密安全的PRNG,例如

• 伯恩斯坦的ChaCha20,RFC 7539.替代品将是
• 吴的HC-256,
• 詹金斯的ISAAC64,或
• DE Shaw的Random123套件(其中包括很好地命名的ARS,用AES-CTR加密无限序列的零的简化),虽然我不确定它们是如何被仔细检查的.

PRNG测试

同样,对于PRNG的统计测试,现在可能是最先进的

• L'Ecuyer的TestU01(带有SmallCrush,Crush,BigCrush),
• 多蒂-汉弗莱的pracrand其PractRand套件,

虽然这些在历史上很重要,但已经过时了:

• Marsaglia的DieHard,DieHarder,
• NIST 800-22 A.

Answer 2

试试MT的继任者:SFMT(http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html).首字母缩略词代表面向SIMD的Fast Mersenne Twister.它使用向量指令(如SSE或AltiVec)来快速生成随机数.

此外,它显示比原始MT更大的周期:SFMT可以配置为使用最多2 ²¹⁶⁰⁹¹ -1的周期.

最后,MT在初始化时出现了一些问题:它往往会抽出大量的0,导致质量差的随机数.在通过算法的重现进行补偿之前,此问题可能持续多达700000次绘制.因此,SFMT也被设计为比其长者更快地离开这个零过剩状态.

检查我在本文开头给出的链接,找到源代码和描述该算法的科学出版物.

为了肯定说服你,你可以在这里看到http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html一个表格,比较MT和SFMT.无论如何,SFMT在提供比MT更好的品质的同时更快.

- 编辑以下评论 -

更一般地说,当您选择PRNG时,您需要考虑您正在开发的应用程序.实际上,一些PRNG更适合某些应用程序约束.例如,MT和WELL生成器不适合加密应用程序,而它们是处理蒙特卡罗模拟时的最佳选择.

在我们的例子中,由于其比SFMT具有更好的等分布特性,WELL可能看起来很理想.尽管如此,WELL也慢得多,并且他无法显示像SFMT那样大的周期.

作为结论,PRNG不能被声明为所有应用程序的最佳选择,而是针对特定域和特定情况.

Answer 3

如果你寻找一个通过所有统计测试的算法,但仍然很快你可以尝试Xorshift算法.与Java中的随机库相比,它的速度提高了约30%,并提供了更好的结果.它的时期不像Mersenne Twister那么长,但它仍然不错.

可以在此处找到实现:

http://demesos.blogspot.com/2011/09/replacing-java-random-generator.html

编辑

似乎XORShift的新变种现在甚至在质量上击败了MerseneTwister和WELL(尽管不是在时期).他们通过了更多的经验质量测试,如PRNG Shootout所示.

它们的性能也令人印象深刻.我在这里做了Java,源和结果的不同实现的基准测试:https: //github.com/tobijdc/PRNG-Performance

Answer 4

1. 通过所有统计测试

到目前为止，其他回复中提到的每个 PRNG 都广泛地属于 PRNG 的 GFSR/LFSR 系列。所有这些都未能通过二进制矩阵秩和可能的线性复杂性测试。

有许多 PRNG 通过了所有通用统计测试，但出于某种原因，人们似乎发现 GFSR 更性感。

这是一个通过所有通用统计测试但不是加密安全的示例 PRNG：

static unsigned long long rng_a, rng_b, rng_c, rng_counter;
unsigned long long rng64() {
    unsigned long long tmp = rng_a + rng_b + rng_counter++;
    rng_a = rng_b ^ (rng_b >> 12);
    rng_b = rng_c + (rng_c << 3);
    rng_c = ((rng_c << 25) | (rng_c >> (64-25))) + tmp;
    return tmp;
}
void seed(unsigned long long s) {
    rng_a = rng_b = rng_c = s; rng_counter = 1;
    for (int i = 0; i < 12; i++) rng64();
}

（假设 long long 是 64 位整数类型......我认为在定义该类型的任何地方都是如此？）

这对于任何正常使用来说都足够了，而且速度也相当快。如果您需要更好的东西，请切换到 CSPRNG - 它们往往比任何非加密 PRNG 好得多。例如，ChaCha ( http://cr.yp.to/chacha.html ) 是一个可靠的 CSPRNG，具有快速播种、随机访问和可调节的质量。HC-256 ( http://en.wikipedia.org/wiki/HC-256 ) 是一种更高质量的 CSPRNG，它的播种速度很慢，但一旦播种就相当快。

2. 即使在非常高的维度上也表现良好

这几乎等同于第 1 点。此外，我提供的示例 PRNG 是混乱类型的 - 这样的 PRNG，当它们行为不端时，会在少量维度而不是大量维度上进行。

3. 有一个非常大的时期

定义极大？

我上面提供的示例 PRNG 的可证明最小周期为 2^64，平均周期为 2^255，状态空间为 2^256。对于我链接的两个 CSPRNG，ChaCha 的周期为 2^68，状态空间为 2^260，而 HC-256 的平均周期约为 2^65000 IIRC，并提供了其最短周期的概率证明长于 2^128，似然大于 1-(2^-128)，状态空间约为 2^65000。

在实践中，周期超过 2^60 并不重要，即使是边际。通常人们要求高周期的原因是因为要么他们不知道他们在说什么，要么是因为他们需要一个大的状态空间（至少等于周期，但通常更大），这可能是有益的到 2^250 左右。但是一个大的状态空间并没有多大帮助，除非你从比单个整数大的东西中播种，而大多数人都没有。

（注：在代码中，^用于表示异或，而在文本中^用于表示指数）