c之为什么 rand() 在 Linux 上比 Mac 更频繁地重复数字

我在 C 中实现了一个 hashmap 作为我正在处理的项目的一部分，并使用随机插入来测试它。我注意到 rand()在 Linux 上似乎比在 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，也无法在网上找到任何内容。谢谢!

请您参考如下方法:

虽然一开始它可能听起来像 macOS rand()不重复任何数字在某种程度上更好，应该注意，生成的数字数量是 expected看到大量重复(实际上，大约 7.9 亿，或 (231-1)/e)。同样，按顺序迭代数字也不会产生重复，但不会被认为是非常随机的。所以 Linux rand()在此测试中，实现与真正的随机源无法区分，而 macOS rand()不是。

乍一看令人惊讶的另一件事是 macOS rand()可以设法避免重复。看着 its source code ，我们发现实现如下:

/* 
 * 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 之间的所有数字，包括，恰好一次，在序列再次重复之前。由于下一个状态基于乘法，因此状态永远不会为零(或所有 future 状态也将为零)。因此，您看到的重复数字是第一个，而零是永远不会返回的数字。

至少自 macOS(或 OS X)存在以来，Apple 一直在其文档和示例中推广使用更好的随机数生成器，因此 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 亿个重复项。