18

在[0, n)中选择随机数的一种常见方法是取rand()模n :的结果rand() % n。但是，即使可用实现返回的结果是完全一致的，当不被n整除时，结果[0, n)数字rand()的一致性是否应该存在问题？例如，假设是 2，n是 2。那么在 3 个可能的输出中：0、1 和 2，当我们使用它们模n时，我们分别得到 0、1 和 0 。因此，输出将根本不均匀。RAND_MAX + 1RAND_MAXrand()

这在实践中是一个真正的问题吗？在[0, n)中均匀地从输出中选择随机数的更好方法是什么rand()，最好没有任何浮点运算？

4

4 回答 4

10

你是对的，rand() % N不是精确均匀分布的。确切地说，重要程度取决于您想要的数字范围和您想要的随机性程度，但是如果您想要足够的随机性以至于您甚至会关心它，那么您无论如何都不想使用它rand()。获取一个真正的随机数生成器。

也就是说，要获得真正的随机分布，请修改 2 的下一个幂并进行采样，直到获得所需范围内的一个（例如，对于 0-9，使用while(n = rand()%0x10 > 10);）。

于 2012-10-27T22:03:07.707 回答
7

这取决于：

  • RAND_MAX 的值
  • 你的 N 值

让我们假设您的 RAND_MAX 是 2^32。如果 N 相当小（假设为 2），则偏差为 1 / 2^31 - 或者太小而无法注意到。

但是如果 N 大很多，比如 2^20，那么偏差是 1 / 2^12，或者大约是 4096 中的 1。大很多，但仍然很小。

于 2012-10-27T21:55:12.247 回答
1

您可以采取的一种方法如下：

知道 的值N，就可以R_MAX = ((RAND_MAX + 1) / N) * N;实现一致性。

所以你可以做你的自定义rand()功能：

int custom_rand(int mod) {
    int x = rand();
    const int R_MAX = ((RAND_MAX + 1) / mod) * mod;    

    while (x > R_MAX) { // discard the result if it is bigger
        x = rand();
    }

    return (x % mod);
}
于 2012-10-27T22:11:57.533 回答
1

将余数（% 不是 C 中的“模”运算符）用于缩小范围内的统一随机数有两个问题。首先是对较小的数字有轻微的偏差（如上所述），其次是典型的 PRNG 在低位比特中往往不太随机。我似乎记得 Knuth （计算机编程的艺术，第二卷，半数字算法）以及声称（在从 MIX 转换为 C 之后）rand()%2 是随机单个位的不良来源。最好选择 (rand() > RAND_MAX/2) （或测试高位，如果 RAND_MAX 接近 2 的幂。）

The remainder should be good enough casual use on small intervals. Avoid it for simulations. Actually, avoid rand() altogether for large simulations or "Monte Carlo" computations. Implementations tend to have a period on the order of 2^32 or less. It's not hard to exceed 4 billion trials on a 2+ GHz processor.

于 2012-10-27T22:42:06.533 回答