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

Question

我正在阅读C FAQ,并在一个问题中发现它建议我使用rand() / (RAND_MAX / N + 1)而不是更流行的方式rand() % N.

这样做的原因是,当数字N为低rand() % N时,只使用几位rand().

我测试了不同的处理办法N是2在Windows和Linux,但不能注意到差别.

#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()以避免偏差.

否则,无论质量如何,都会遇到这个问题rand().简而言之,问题在于你将该范围切割成每个长度的多个"部分" N,如果N不分割范围则最后部分将不完整.因此,从该部分"切断"的数字不太可能发生,因为它们可以从中生成更少的"部分".

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

上面提到的问题是非常基本的,除非Y除以X,否则无法在Y结果上均匀分布X个不同的值.您可以通过拒绝一部分随机样本来修复它,使Y除以新的X.