c++ - 为什么 rand()%6 有偏见？

Question

在阅读如何使用 std::rand 时，我在 cppreference.com 上找到了这段代码

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

右边的表达有什么问题？试过了，效果很好。

Answer 1

rand() % 6 有两个问题(1+ 不会影响任何一个问题)。

首先，正如几个答案所指出的，如果 rand() 的低位不适当统一，则余数运算符的结果也不统一。

其次，如果 rand() 产生的不同值的数量不是 6 的倍数，那么余数将产生比高值更多的低值。即使 rand() 返回完美分布的值也是如此。

作为一个极端的例子，假设 rand() 在 [0..6] 范围内产生均匀分布的值。如果您查看这些值的余数，当 rand() 返回 [0..5] 范围内的值时，余数会在该范围内产生均匀分布的结果[0..5]。当 rand() 返回 6 时，rand() % 6 返回 0，就像 rand() 返回 0。所以你得到一个0 的数量是任何其他值的两倍。

第二个是rand() % 6的真正问题。

避免该问题的方法是丢弃会产生不一致重复的值。您计算小于或等于 RAND_MAX 的 6 的最大倍数，并且每当 rand() 返回大于或等于该倍数的值时，您拒绝它并调用`rand() 再次，根据需要多次。

所以:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

这是所讨论代码的不同实现，旨在更清楚地显示正在发生的事情。