你可以建立一个最大的力量的两个大于n的rng,如你所描述的.然后每当该算法生成大于n-1的数字时,将该数字丢弃,然后重试.这被称为拒绝的方法.
加成
算法是
Let m = 2^k >= n where k is is as small as possible.
do
Let r = random number in 0 .. m-1 generated by k coin flips
while r >= n
return r
这个循环最多停止迭代的概率由1 – (1/2)^ i限定.这一速度非常快速：循环仍然运行30次迭代,概率小于十亿分之一.
您可以使用稍微修改的算法减少预期的迭代次数：
Choose p >= 1
Let m = 2^k >= p n where k is is as small as possible.
do
Let r = random number in 0 .. m-1 generated by k coin flips
while r >= p n
return floor(r / p)
例如,如果我们尝试用更简单的算法生成0 .. 4(n = 5),我们将拒绝5,6和7,这是结果的3/8. p = 3(例如),pn = 15,我们将有m = 16,并且只拒绝15或1/16的结果.价格需要四个硬币翻转而不是3和一个分区op.您可以继续增加p并添加硬币翻转,以尽可能减少拒绝.
