c++ - 当摆脱模偏差时，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 进行换行/sup>。 (假定 limit 的类型不小于 int，这将导致它被提升为 int 并使用带符号的算术，并且代码可能会中断。)然后识别 2w−limit 与 2w/sup> 模 limit。因此 -limit % limit 产生 2w 除以 limit 的余数。设为 min。}

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

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

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