随机数的均匀性所采取模N [英] Uniformity of random numbers taken modulo N

问题描述

在选择一个随机数的一种常见方法的 [0，N）的是采取的结果兰特（）模的 ñ的兰特（）％N 。然而，即使由可用兰特（）实现所返回的结果是完全均匀的，不应该存在是一个问题与所得的 [0的均匀性， N）的数字时 RAND_MAX + 1 不通过的 N 的平均分配？例如。假设 RAND_MAX 2，而 N 的是2。然后出3种可能的 RAND（）的输出：0，1和2，我们得到0，1和0分别当我们使用这些模<青霉> N 的。因此，输出将是不均匀的。

One common way of choosing a random number in [0, n) is to take the result of rand() modulo n: rand() % n. However, even if the results returned by the available rand() implementation are fully uniform, shouldn't there be a problem with the uniformity of the resulting [0, n) numbers when RAND_MAX + 1 does not divide evenly by n? E.g. suppose RAND_MAX is 2, and n is 2. Then out of 3 possible rand() outputs: 0, 1 and 2, we get 0, 1 and 0 respectively when we use them modulo n. Therefore the output will not be uniform at all.

这是在实践中真正的问题？什么是的 [0，N）的从兰特均匀导出（）输出，preferably选择随机数没有任何漂浮更好的办法浮点运算？

Is this a real problem in practice? What is a better way of choosing random numbers in [0, n) uniformly deriving from rand() output, preferably without any floating point arithmetic?

推荐答案

您是正确的，兰特（）％N 不是precisely均匀分布。 precisely多少的事项取决于你想要的数字范围，你想随机性的程度，但如果你想足够的随机性，你甚至会关心它，你不希望使用兰特（）反正。得到真正的随机数发生器。

You are correct, rand() % N is not precisely uniformly distributed. Precisely how much that matters depends on the range of numbers you want and the degree of randomness you want, but if you want enough randomness that you'd even care about it you don't want to use rand() anyway. Get a real random number generator.

这表示，要得到真正的随机分布，MOD为2的下一个动力和样品，直到你的范围得到一个你希望（如0-9，使用而（N =兰特（）％0×10→10）; ）

That said, to get a real random distribution, mod to the next power of 2 and sample until you get one in the range you want (e.g. for 0-9, use while(n = rand()%0x10 > 10);).

这篇关于随机数的均匀性所采取模N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！