为什么rand()％6有偏见? [英] Why is rand()%6 biased?

问题描述

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

When reading how to use std::rand, I found this code on cppreference.com

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

右边的表达式有什么问题?尝试了一下，效果很好.

What is wrong with the expression on the right? Tried it and it works perfectly.

推荐答案

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

There are two issues with rand() % 6 (the 1+ doesn't affect either problem).

首先，正如几个答案所指出的那样，如果rand()的低位没有适当地统一，则余数运算符的结果也将不一致.

First, as several answers have pointed out, if the low bits of rand() aren't appropriately uniform, the result of the remainder operator is also not uniform.

第二，如果rand()产生的不同值的数量不是6的倍数，则其余部分将产生比高值更多的低值.即使rand()返回完美分布的值也是如此.

Second, if the number of distinct values produced by rand() is not a multiple of 6, then the remainder will produce more low values than high values. That's true even if rand() returns perfectly distributed values.

作为一个极端示例，假设rand()产生范围[0..6]的均匀分布值.如果查看这些值的余数，则当rand()返回范围为[0..5]的值时，余数将生成范围为[0..5]的均匀分布的结果.当rand()返回6时，rand() % 6返回0，就像rand()返回0一样.因此，您获得的0分配是其他任何值的两倍.

As an extreme example, pretend that rand() produces uniformly distributed values in the range [0..6]. If you look at the remainders for those values, when rand() returns a value in the range [0..5], the remainder produces uniformly distributed results in the range [0..5]. When rand() returns 6, rand() % 6 returns 0, just as if rand() had returned 0. So you get a distribution with twice as many 0's as any other value.

第二个是rand() % 6的 real 问题.

避免该问题的方法是舍弃那些可能产生不一致重复项的值.您计算出小于或等于RAND_MAX的6的最大倍数，并且每当rand()返回的值大于或等于该倍数时，您就拒绝它并再次调用`rand()，这是需要的多次.

The way to avoid that problem is to discard values that would produce non-uniform duplicates. You calculate the largest multiple of 6 that's less than or equal to RAND_MAX, and whenever rand() returns a value that's greater than or equal to that multiple you reject it and call `rand() again, as many times a needed.

所以:

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

这是所讨论代码的另一种实现，旨在更清楚地显示正在发生的事情.

That's a different implementation of the code in question, intended to more clearly show what's going on.

这篇关于为什么rand()％6有偏见?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！