随机数,范围为0到n

Question

给定一个产生真随机32位数的函数R,我想要一个返回0到n范围内随机整数的函数,其中n是任意的(小于2 ^ 32).

该函数必须以相同的概率产生0到n的所有值.

我想要一个在没有if语句或循环的情况下在常量时间内执行的函数,所以像Java Random.nextInt(n)函数这样的东西就出来了.

我怀疑一个简单的模数不会起作用,除非n是2的幂 - 我是对的吗？

---

我接受了Jason的答案,尽管它需要一个不确定持续时间的循环,因为它似乎是在实践中使用的最佳方法,并且基本上回答了我的问题.然而,我仍然对任何算法(即使效率较低)感兴趣,这些算法本质上是确定性的并且保证终止,例如Mark Byers指出的.

Answer 1

在不丢弃源中的某些值的情况下,您无法执行此操作.例如,不能将一组大小为2 ^ 32的区域划分为三个大小相等的组.因此,如果不丢弃某些值并迭代直到产生非丢弃值,则不可能这样做.

所以,只需使用此(伪代码):

rng is random number generator produces uniform integers from [0, max)
compute m = max modulo (n + 1)
do {
    draw a random number r from rng
} while(r >= max - m)
return r modulo (n + 1)

实际上,我正在抛出导致问题的分布的顶部.如果rng是统一的[0, max),那么这个算法将是统一的[0, n]