取模 N 的随机数的一致性 [英] Uniformity of random numbers taken modulo N

问题描述

在 [0, n) 中选择随机数的一种常见方法是取 rand() 模 n 的结果:rand() % n.但是，即使可用的 rand() 实现返回的结果是完全统一的，结果 [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) 中选择随机数的更好方法是什么，从 rand() 输出统一派生，最好没有任何浮点运算?

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?

推荐答案

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

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.

也就是说，要获得真正的随机分布，请修改为 2 的下一个幂并进行采样，直到获得所需范围内的一个(例如，对于 0-9，使用 while(n = rand()%0x10 > 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屋！