4

我正在尝试实现一个可容忍质量的rand_r接口版本，它有一个不幸的接口要求，即它的整个状态都存储在一个 type 对象中unsigned，就我的目的而言，这意味着正好是 32 位。另外，我需要它的输出范围是[0,2³¹-1]. 标准解决方案是使用 LCG 并丢弃低位（具有最短周期），但这仍然为接下来的几位留下非常糟糕的周期。

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

由于只有 32 位状态，PRNG 的周期以 2³² 为界，并且为了无偏差，如果 PRNG 具有完整周期，则每个值必须准确输出两次，如果周期为 2³²，则必须准确输出一次。较短的时期不能是无偏见的。

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

4

4 回答 4

4

提供非常高质量的一种好的（但可能不是最快的）可能性是在CTR 模式下使用 32 位分组密码。基本上，您的 RNG 状态只是一个 32 位计数器，每次调用 RNG 时都会加一，输出将是使用带有任意选择的固定密钥的分组密码对该计数器值进行加密。对于额外的随机性，您甚至可以提供一个（非标准）函数让用户设置自定义键。

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

（编辑：我的错，XXTEA 只下降到 64 位。但是，正如 CodesInChaos 在评论中所建议的，Skip32可能是另一种选择。或者您可以构建自己的 32 位Feistel 密码。）

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

使用 CTR 模式还提供了一些您可能会觉得方便的额外功能（即使它们不是您正在开发的官方 API 的一部分），例如能够快速查找 RNG 输出流中的任何点，只需添加或从状态中减去。

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

于 2013-06-11T03:32:57.637 回答
3

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

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

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

于 2013-06-11T03:05:00.340 回答
3

除了使用Lehmer MCG之外，您还可以使用以下几种：

Xorshift的32 位变体使用 32 位状态保证周期为 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 xorshift32amx(void) {
    int s = __builtin_bswap32(state * 1597334677);
    state ^= state << 13;
    state ^= state >> 17;
    state ^= state << 5;
    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 次测试，没有失败，并且在 4GB 生成的数据上，总 P 值为 0.984（其中 1 是完美的，0.1 或更少是失败）。这是整个周期的四分之一”。它似乎是对 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 *= 0xc2b2ae35;
    return z ^= z >> 16;
}

这里的质量可能有问题，但它的 64 位大哥有很多粉丝（通过 BigCrush）。所以总体结构值得一看。

于 2018-08-28T10:55:30.347 回答
2

详细说明我的评论...

计数器模式下的分组密码以大约以下形式提供生成器（使用更大的数据类型除外）：

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

由于尚未指定加密安全性（并且在 32 位中它或多或少是徒劳的），一个更简单的临时调和函数应该可以解决问题。

一种方法是next()函数简单（例如，return state + 1;）并temper()通过复杂（如分组密码）进行补偿。

一个更平衡的方法是在 中实现 LCG next()，因为我们知道它也访问所有可能的状态，但以随机（ish）顺序，并找到一个实现temper()足以解决 LCG 剩余问题的实现。

Mersenne Twister 在其输出中包含这样的回火功能。那可能是合适的。此外，此问题要求满足要求的操作。

我有一个最喜欢的方法，就是对单词进行位反转，然后将其乘以某个常数（奇数）数。如果位反转不是您架构上的本机操作，那可能过于复杂。

于 2013-06-11T23:33:58.417 回答