6

为什么这段代码会生成均匀分布的数字？我理解它有一些困难。有人可以解释一下吗？谢谢。

int RandomUniform(int n) {  
  int top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;  
  int r;  
  do {  
    r = rand();  
  } while (r > top);  
  return (r % n);  
}

更新：我明白为什么 rand()%n 没有给你一个均匀分布的序列。我的问题是为什么

top = ((((RAND_MAX - n) + 1) / n) * n - 1) + n;

这里有什么顾虑？我认为一个简单的 top = RAND_MAX / n * n 就可以了。

4

3 回答 3

10

函数假设rand()是均匀分布的；这是否是一个有效的假设取决于rand().

给定一个制服，我们可以通过计算rand()得到一个范围内的随机数。但是，总的来说，这不会很统一。例如，假设是 3 和7：[0,n)rand()%nnRAND_MAX

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 0 1

我们可以看到 0 和 1 的概率为 3/8，而 2 的概率仅为 2/8：分布不均匀。

您的代码会丢弃任何rand()大于或等于n它可以生成的最大倍数的值。现在每个值都有相等的概率：

rand()      0 1 2 3 4 5 6 7
rand() % n  0 1 2 0 1 2 X X

所以 0,1 和 2 都得出 1/3 的概率，只要我们不是那么倒霉以至于循环永远不会终止。

关于您的更新：

我认为一个简单的 top = RAND_MAX / n * n 就可以了。

如果RAND_MAX是排他界限（比实际最大值多一个），那将是正确的。既然是包容界限，我们需要加一个来得到独占界限；并且由于以下逻辑与>包含边界进行比较，因此在计算后再次减去：

int top = ((RAND_MAX + 1) / n) * n - 1;

但是，如果RAND_MAX等于INT_MAX，则计算会溢出；为避免这种情况，n请在计算开始时减去，然后在末尾再次添加：

int top = (((RAND_MAX - n) + 1) / n) * n - 1 + n;
于 2013-02-04T15:45:40.590 回答
7

根本问题是这样的：假设您有一个随机数生成器my_rand()，它产生 0 到 6（含）的值，并且您想要生成 0 到 5（含）的值；如果您运行生成器并返回my_rand() % 6，您将不会得到均匀分布。当my_rand()返回 0 时，你得到 0；当它返回 1 时，你会得到 1，以此类推，直到my_rand()返回 6；在这种情况下my_rand() % 6是 0。所以总的来说，my_rand() % 6返回 0 的频率是任何其他值的两倍。解决这个问题的方法是不要使用大于 5 的值，也就是说，不要my_rand() % 5编写一个循环并丢弃my_rand()太大的值。这基本上就是问题中的代码正在做的事情。我没有追查过，但通常的实现是计算最大的倍数n小于或等于RAND_MAX，并且每当rand()返回大于该倍数的值时，返回并获取新值。

于 2013-02-04T15:40:16.950 回答
2

我没有跟踪计算顶部的代码，而是可以返回RAND_MAX的最大值；将是一个更好的上限，但如果是，比如说，结果将是不可预测的。所以也许所有的代码都试图避免溢出。rand()(RAND_MAX + 1) / n * nRAND_MAXINT_MAX

于 2013-02-04T16:02:07.520 回答