当摆脱模偏差时，min = -upper_bound % upper_bound; // 工作？

Question

在answers to this other question中，提供了以下解决方案，由 OpenBSD 提供，为简洁起见重写，

uint32_t foo( uint32_t limit ) {
  uint32_t min = -limit % limit, r = 0;

    for(;;) {
      r = random_function();
      if ( r >= min ) break;
    }
    return r % limit;
 }

uint32_t min = -limit % limit 行究竟是如何工作的？我想知道的是，是否有数学证明它确实计算了随机数的某个下限并充分消除了模偏差？

Answer 1

在-limit % limit中，考虑-limit产生的值是2^w−limit，其中 w 是正在使用的无符号类型的位宽度，因为无符号算术被定义为对模 2^{w[=93 进行换行=]}。（假设 limit 的类型不窄于 int，这将导致它被提升为 int 并使用带符号的算术，并且代码可能会中断。）然后认识到2^w−limit 等同于 2^w模limit。所以 -limit % limit 产生 2^w 除以 limit 的余数。设为 min.

在整数集合{0,1,2,3,…2^w−1}中，一个有余数的数r (0 ≤ r < limit) 除以 limit 时至少出现 floor(2^w/limit) 次。我们可以识别它们中的每一个：对于 0 ≤ q < floor(2^w/limit), q•limit + r 有余数 r 并且在放。如果 0 ≤ r < min，则集合中还有一个这样的数，其中 q = floor(2^w/limit)。这些占集合 {0, 1, 2, 3,… 2^w−1} 中的所有数字，因为 floor(2^w/limit)•limit + min = 2^w，这样我们的计数就完成了。对于r个不同的余数，有floor(2^w/limit)+1集合中具有该余数的数字，对于 min−r 其他余数，有 floor(2^w/limit) 以及集合中的余数。

现在假设我们从这个集合{0, 1, 2, 3, ... 2^w−1中随机抽取一个数}.显然，余数为 0 ≤ r < min 的数字可能会稍微频繁出现，因为集合中的数字更多。通过拒绝每个此类数字的一个实例，我们将它们排除在我们的分布之外。实际上，我们是从集合 { min, min+1, min+2,… 2^w−1}。结果是一个分布，每个数字都有 floor(2^w/limit) 次出现，并且有特定的余数。

由于每个余数在有效分布中出现的次数相同，因此每个余数都有相同的机会被统一抽签选中。

当摆脱模偏差时，min = -upper_bound % upper_bound; // 工作？

When getting rid of modulo bias how does min = -upper_bound % upper_bound; // work?

c

c++

random

modulo