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

我正在用 C 语言实现一个散列表，这是我正在做的一个项目的一部分，我使用随机插入来测试它。我注意到，与 Mac 相比，Linux 上的 rand()似乎更经常地重复数字。两个平台上的 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 使用，也不能在网上找到任何东西。谢谢！

8473 次浏览
小开

rand()是由 C 标准定义的，C 标准没有指定使用哪种算法。显然，Apple 使用的算法比 GNU/Linux 实现的算法要差: Linux 的算法与测试中的真正随机源代码没有什么区别，而 Apple 的实现只是改变了一些数字。

If you want random numbers of any quality, either use a better PRNG that gives at least some guarantees on the quality of the numbers it returns, or simply read from /dev/urandom or similar. The later gives you cryptographic quality numbers, but is slow. Even if it is too slow by itself, /dev/urandom can provide some excellent seeds to some other, faster PRNG.

小开

MacOS 在 stdlib 中提供了一个未记录的 rand ()函数。如果不进行播种，那么它输出的第一个值是16807、282475249、1622650073、984943658和1144108930。快速搜索将显示该序列对应于一个非常基本的 LCG 随机数发生器，该发生器迭代以下公式:

X n+1 = 75 · X[俄语](模数231 & -1)

由于这个 RNG 的状态完全由一个32位整数的值来描述，所以它的周期不是很长。确切地说，它每231 & -2次迭代重复自己，输出从1到231 & -2的每个值。

我不认为所有版本的 Linux 都有 rand ()的 标准实现，但是有一个 Glibc rand ()函数经常被使用。它不使用单个32位状态变量，而是使用一个超过1000位的池，从各种意图和目的来看，它永远不会产生一个完全重复的序列。同样，您可以通过打印来自这个 RNG 的前几个输出，而不需要首先播种，就可以找到您所拥有的版本。(glibc rand ()函数生成数字1804289383、846930886、1681692777、1714636915和1957747793。)

所以在 Linux 中碰撞越来越多(在 MacOS 中几乎没有碰撞)的原因是 Linux 版本的 rand ()基本上更加随机。

小开

一般来说，由于低阶位显示的随机性比高阶位要小，所以长期以来，兰德/沙德对被认为是不适用的。这可能与您的结果无关，也可能与您的结果无关，但我认为这仍然是一个很好的机会来记住，即使一些 rand/sand 实现现在更新，旧的实现仍然存在，最好使用随机(3)。在我的 Arch Linux 机器上，下面的注释仍然在 rand (3)的手册页中:

  The versions of rand() and srand() in the Linux C Library use the  same
random number generator as random(3) and srandom(3), so the lower-order
bits should be as random as the higher-order bits.  However,  on  older
rand()  implementations,  and  on  current implementations on different
systems, the lower-order bits are much less random than the  higher-or-
der bits.  Do not use this function in applications intended to be por-
table when good randomness is needed.  (Use random(3) instead.)

在这之下，手册页实际上给出了非常简短、非常简单的 RAND 和 sand 的实现示例，它们大约是你见过的最简单的 LC RNGs，并且有一个小的 RAND _ MAX。我不认为它们与 C 标准库中的内容相匹配，如果它们曾经匹配过的话。至少我希望不是。

一般来说，如果要使用标准库中的内容，尽可能使用 Random (手册页将其列为 POSIX 标准，可追溯到 POSIX.1-2001，但 rand 在 C 标准化之前就已经是标准了)。或者更好的办法是，打开数字食谱(或者在网上查找)或者 Knuth，然后实现一个。它们真的很简单，你只需要做一次，就可以拥有一个通用的 RNG，其中包含你最常需要的属性和已知的质量。

小开
最佳答案

虽然一开始听起来似乎 macOS rand()不重复任何数字比较好，但是我们应该注意到，在产生这么多数字的情况下，意料之中可以看到大量的重复(实际上，大约7.9亿，或者(231-1)/好吧)。同样，按顺序迭代这些数字也不会产生重复，但不会被认为是非常随机的。因此，Linux rand()实现与真正的随机源没有什么区别，而 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)存在的时候，苹果就一直在推广使用更好的随机数生成器，所以 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亿个重复。


提交答案