时间戳

首页 > 解决方案 > 为什么 rand() 在 Linux 上重复数字的频率远高于 Mac？

c - 为什么 rand() 在 Linux 上重复数字的频率远高于 Mac？

问题描述

作为我正在处理的项目的一部分，我在 C 中实现了一个 hashmap，并使用随机插入来测试它。我注意到rand()在 Linux 上似乎比在 Mac 上更频繁地重复数字。RAND_MAX在2147483647/0x7FFFFFFF两个平台上。我已将其简化为这个测试程序，该程序生成一个长字节数组RAND_MAX+1，生成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，也无法在网上找到任何内容。谢谢！

标签： clinuxmacosrandom

解决方案

虽然起初听起来 macOSrand()在不重复任何数字方面更好，但应该注意的是，由于生成了这么多数字，预计会看到大量重复（实际上，大约 7.9 亿，或（2 31 -1 )/ e )。同样，按顺序遍历数字也不会产生重复，但不会被认为是非常随机的。因此，在这个测试中，Linuxrand()实现与真正的随机源无法区分，而 macOS则不然。rand()

乍一看令人惊讶的另一件事是 macOS 如何rand()能够很好地避免重复。查看它的源代码，我们发现实现如下：

/*
 * 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（含）之间的所有数字恰好一次。由于下一个状态基于乘法，因此状态永远不会为零（或所有未来状态也将为零）。因此，您看到的重复数字是第一个数字，而零是永远不会返回的数字。

至少只要 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 亿次重复。

推荐阅读