寻找体面质量的PRNG只有32位状态

我正在尝试实现rand_r接口的可容忍质量版本,该接口具有令人遗憾的接口要求,即其整个状态存储在unsigned类型的单个对象中,对于我的目的而言,这意味着正好是32位。 另外,我需要它的输出范围是[0,2³¹-1] 。 标准解决方案是使用LCG并丢弃低位(具有最短周期),但这仍然为接下来的几位留下非常差的周期。

我最初的想法是使用LCG的两次或三次迭代来生成输出的高/低或高/中/低位。 但是,这种方法不能保持无偏差的分布; 而不是每个输出值具有相同的频率,许多输出多次出现,而有些则根本不发生。

由于只有32位状态,PRNG的周期以2 32为界,并且为了没有偏置,PRNG必须输出每个值,如果它具有完整周期则恰好输出两次,如果它具有周期2 3,则必须输出一次。 较短的时期不能没有偏见。

是否有任何知名的PRNG算法符合这些标准?

提供高质量的一个好(但可能不是最快)的可能性是在CTR模式下使用32位分组密码 。 基本上,您的RNG状态只是一个32位计数器,对于每个RNG呼叫增加1,并且输出将是使用具有一些任意选择的固定密钥的分组密码对该计数器值的加密。 为了获得额外的随机性,您甚至可以提供(非标准)function来让用户设置自定义密钥。

通常使用的32位块密码并不多,因为这种短块大小会给加密使用带来问题。 (基本上, 生日悖论让你可以在仅仅约2 16 = 65536输出之后以不可忽略的概率区分这种密码的输出与随机函数,并且在2 32输出之后,非随机性显然变得确定。)但是,一些具有可调整块大小的密码(例如XXTEA或HPC )将允许您降低到32位,并且应该适合您的目的。

编辑:我的不好,XXTEA只下降到64位。但是,正如在评论中的CodesInChaos所建议的那样, Skip32可能是另一种选择。或者你可以构建自己的32位Feistel密码 。)

CTR模式构造保证RNG将具有2 32个输出的完整周期,而(非破坏)分组密码的标准安全声明基本上是将它们的输出与集合的随机排列区分开在计算上是不可行的。 32位整数。 (当然,如上所述,这种置换仍然很容易与采用32位值的随机函数区分开来。)

使用CTR模式还提供了一些您可能会觉得方便的额外function(即使它们不是您正在开发的官方API的一部分),例如只需添加或快速搜索到RNG输出流中的任何点的function。从州中减去。

另一方面,您可能希望通过将内部状态设置为种子值来遵循播种RNG的常规做法,因为这会导致从附近种子生成的输出流高度相似(基本上只是相同的流因种子的差异而移动)。 避免此问题的一种方法是在播种过程中添加额外的加密步骤,即使用密码加密种子并将内部计数器值设置为等于结果。

阐述我的评论……

计数器模式下的块密码以大致以下forms给出生成器(除了使用更大的数据类型):

 uint32_t state = 0; uint32_t rand() { state = next(state); return temper(state); } 

由于没有指定加密安全性(并且在32位中它或多或少是徒劳的),因此更简单的临时调节function应该可行。

一种方法是next()函数是简单的(例如, return state + 1; )和temper()通过复杂来补偿(如在块密码中)。

更平衡的方法是在next()实现LCG,因为我们知道它也会以随机(ish)顺序访问所有可能的状态,并找到temper()的实现,它只能完成剩下的工作来覆盖其余的LCG的问题。

Mersenne Twister在其输出上包含这样的调节function。 这可能是合适的。 此外, 该问题要求满足要求的操作。

我有一个最喜欢的,就是将该位反转,然后将它乘以一些常数(奇数)。 如果位反转不是架构上的本机操作,那可能会过于复杂。

32位最大周期Galois LFSR可能适合您。 尝试:

 r = (r >> 1) ^ (-(r & 1) & 0x80200003); 

LFSR的一个问题是你不能产生值0.所以这一个的范围是1到2 ^ 32-1。 您可能想要调整输出,或者坚持使用良好的LCG。

除了使用Lehmer MCG ,还有一些你可以使用:

使用32位状态时,32位Xorshift变体的保证周期为2 32 -1

 uint32_t state; uint32_t xorshift32(void) { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state; } 

这是2003年的原始32位推荐(见论文)。 根据您对“体面质量”的定义,这应该没问题。 然而,它没有通过Diehard的二进制排名测试和SmallCrush的5/10测试。

具有更好混合和常量的替代版本(通过SmallCrush和Crush)

 uint32_t xorshift32a(void) { int s = __builtin_bswap32(state * 1597334677); state ^= state << 25; state ^= state >> 7; state ^= state << 2; return state + s; } 

基于这里和这里的研究。


还有Mulberry32 ,它的周期恰好是 2 32

 uint32_t mulberry32(void) { uint32_t z = state += 0x6D2B79F5; z = (z ^ z >> 15) * (1 | z); z ^= z + (z ^ z >> 7) * (61 | z); return z ^ z >> 14; } 

这可能是您最好的选择。 它非常好/快。 作者陈述“它通过gjrand的13次测试,没有失败,总P值为0.984(其中1是完美的,0.1或更少是失败的),4GB的生成数据。这是整个时期的四分之一”。 它似乎比SplitMix32有所改进。


“splitMix32”,采用xxHash / MurmurHash3(Weyl序列)

 uint32_t splitmix32(void) { uint32_t z = state += 0x9e3779b9; z ^= z >> 15; // 16 for murmur3 z *= 0x85ebca6b; z ^= z >> 13; z *= 0xc2b2ae3d; // 0xc2b2ae35 for murmur3 return z ^= z >> 16; } 

还有一个完整的2 32周期。 这里的质量可能有问题,但它的64位大哥有很多粉丝 (通过BigCrush)。 所以一般结构值得关注。