选择随机数的一种常用方法 [0,n) 是取结果的 rand()
模 ñ: rand() % n
。但是,即使结果由可用返回 rand()
实施是完全统一的,不应该产生均匀性的问题 [0,n) 数字时 RAND_MAX + 1
不均匀分配 ñ?例如。假设 RAND_MAX
是2,和 ñ 是2.然后有3个可能 rand()
输出:0,1和2,当我们使用模数时,我们分别得到0,1和0 ñ。因此输出将根本不均匀。
这在实践中是一个真正的问题吗?什么是选择随机数的更好方法 [0,n) 统一来源于 rand()
输出,最好没有任何浮点运算?
你是对的, rand() % N
并不是精确均匀分布的。确切地说,重要的是多少取决于你想要的数字范围和你想要的随机程度,但如果你想要足够的随机性,你甚至不关心它,你不想使用它 rand()
无论如何。获得一个真正的随机数生成器。
也就是说,要得到一个真正的随机分布,mod到下一个2的幂并进行采样,直到你得到一个你想要的范围(例如0-9,使用 while(n = rand()%0x10 > 10);
)。
这取决于:
我们假设你的RAND_MAX是2 ^ 32。如果N相当小(假设为2)那么偏差是1/2 ^ 31 - 或者太小而不能注意到。
但是如果N相当大,比如2 ^ 20,那么偏差是1/2 ^ 12,或者在4096中约为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);
}
使用余数(%不是C中的“模”运算符)对于减小范围内的均匀随机数存在两个问题。首先是对较小数字(如上所述)存在轻微偏差,其次是典型PRNG在低阶位中往往较不随机。我似乎记得Knuth(计算机编程艺术,第二卷,数值算法)以及(从MIX转换为C之后)rand()%2是随机单位的不良来源。最好选择(rand()> RAND_MAX / 2)(或测试一个高位,如果RAND_MAX几乎是2的幂)
剩余部分应该足够好,可以在很短的时间内随意使用。避免用于模拟。实际上,对于大型模拟或“蒙特卡罗”计算,完全避免使用rand()。实现往往具有大约2 ^ 32或更小的周期。在2+ GHz处理器上进行超过40亿次试验并不难。