为什么 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

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

原文由 yO_ 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

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

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

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

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

所以：

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

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

原文由 Pete Becker 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这里有隐藏的深度：

1. 小号 u 在 RAND_MAX + 1u 中的使用。 RAND_MAX 被定义为 int 类型，并且通常是最大可能的 int 。 RAND_MAX + 1 的行为在您溢出 signed 类型的情况下是 未定义 的。写入 1u 强制类型转换 RAND_MAX 到 unsigned ，从而避免溢出。

2. % 6 的使用 _可以_（但在 std::rand 我见过的每个实现中 _都不会_）引入任何额外的统计偏差，超出所提供的替代方案。 % 6 是危险的这种情况是数字生成器在低位具有相关性的情况，例如 rand 的相当著名的 IBM 实现（在 C 中），我认为，1970年代将高位和低位翻转为“最后的繁荣”。进一步的考虑是 6 非常小 cf。 RAND_MAX ，所以如果 RAND_MAX 不是 6 的倍数，它可能不是 6 的倍数。

总之，这些天，由于它的易处理性，我会使用 % 6 。除了生成器本身引入的统计异常之外，它不太可能引入任何统计异常。如果您仍有疑问，请 测试 您的生成器以查看它是否具有适合您的用例的统计属性。

原文由 Bathsheba 发布，翻译遵循 CC BY-SA 3.0 许可协议