c - 我应该使用 "rand % N"还是 "rand()/(RAND_MAX/N + 1)"？

Question

我正在阅读 C FAQ并在 question 中找到它建议我使用 rand()/(RAND_MAX/N + 1) 而不是更流行的方式 rand() % N。

这样做的原因是，当 N 是一个小数时，rand() % N 将只使用 rand() 中的几个位>.

我在 Windows 和 Linux 上测试了 N 为 2 的不同方法，但没有注意到差异。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 2

int main(void)
{
    srand(0);
    printf("rand() %% N:\n");
    for (int i = 0; i < 40; ++i) {
        printf("%d ", rand() % N);
    }
    putchar('\n');

    srand(0);
    printf("rand() / (RAND_MAX / N + 1):\n");
    for (int i = 0; i < 40; ++i) {
        printf("%d ", rand() / (RAND_MAX / N + 1));
    }
    putchar('\n');

    return 0;
}

输出是这样的(在我的 gnu/linux 机器上):

rand() % N:
1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 
rand() / (RAND_MAX / N + 1):
1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 

这两种选择对我来说都是完全随机的。甚至看起来第二种方法比 rand % N 更糟糕。

我应该使用 rand() % N 还是 rand()/(RAND_MAX/N + 1)？

Answer 1

如果 N 是 2 的幂，使用余数技术通常是安全的(RAND_MAX 通常是 2 的幂减 1，所以整个范围有一个幂两个长度)。更一般地，N 必须划分 rand() 的范围以避免偏差。

否则，您会遇到 this problem ，无论 rand() 的质量如何。简而言之，问题是您将该范围分成多个“部分”，每个部分的长度为 N，如果 N 不划分范围，则最后一部分不会完整。因此，从该部分“截断”的数字不太可能出现，因为它们可以从中生成的“部分”少了一个。

不幸的是 rand()/(RAND_MAX/N + 1) 也被破坏了(以几乎相同的方式)，所以真正的答案是:不要使用它们中的任何一个。

上面概述的问题确实很根本，除非 Y 除以 X，否则无法在 Y 结果上均匀分配 X 的不同值。您可以通过拒绝部分随机样本来解决这个问题，让 Y 除以新的 X .