为什么兰德（）在Linux上重复数字的频率远远高于Mac？

Question

我在一个项目中用C实现了一个hashmap,并使用随机插入来测试它。我注意到Linux上的rand()似乎比Mac上重复数字的频率要高得多。rand_max在两个平台上都是2147483647/0x7fffffff。我将它简化为一个测试程序，它创建一个字节数组rand_max+1-long，生成rand_max随机数，注意每个随机数是否重复，并从列表中检查。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main() {
    size_t size = ((size_t)RAND_MAX) + 1;
    char *randoms = calloc(size, sizeof(char));
    int dups = 0;
    srand(time(0));
    for (int i = 0; i < RAND_MAX; i++) {
        int r = rand();
        if (randoms[r]) {
            // printf("duplicate at %d\n", r);
            dups++;
        }
        randoms[r] = 1;
    }
    printf("duplicates: %d\n", dups);
}

Linux始终如一地生成了大约7.9亿个副本。Mac始终如一地只生成一个，因此它几乎不重复地遍历它可以生成的每个随机数。谁能给我解释一下这是怎么工作的吗？我分不清与man页面有什么不同，分不清每个人在使用哪一个RNG，在网上也找不到任何东西。谢谢！

Answer 1

虽然一开始听起来好像macOSrand()在不重复任何数字方面更好，但我们应该注意到，随着生成的数字数量的增加，预计会出现大量的重复（实际上，大约有7.9亿个，或者(2³¹-1)/e)。同样地，按顺序迭代数字也不会产生重复，但不会被认为是非常随机的。因此，在本测试中，Linux的rand()实现与真正的随机源无法区分，而macOS的rand()则不然。

第一眼看上去令人惊讶的另一件事是macOSrand()如何能够很好地避免重复。查看其源代码，我们发现实现如下：

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

这确实会导致在序列再次重复之前，在1和rand_max之间的所有数字（包括1和rand_max之间）恰好出现一次。因为下一个状态是基于乘法的，所以这个状态永远不可能是零（或者以后所有的状态也都是零）。因此，你看到的重复数是第一个，而零是永远不会返回的那个。

至少在macOS（或OS X）存在的时候，苹果就一直在他们的文档和示例中推广使用更好的随机数生成器，所以rand()的质量可能并不重要，他们只是坚持使用一种最简单的伪随机数生成器。（正如您所注意到的，他们的rand()甚至被注释为建议改用arc4random()。）

与此相关的一点是，我能找到的最简单的伪随机数生成器是xorshift*，它能在这个（和许多其他）随机性测试中产生良好的结果：

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

这个实现在您的测试中几乎精确地产生了7.9亿个重复。