如何实现只有Random(0,1)的Random(a,b)？

Question

可能重复:
如何通过已知的穿制随机函数RANDOM(0,1)在a,b之间获得均匀随机

在算法简介一书中,有一个消息:

描述只调用Random(0,1)的过程Random(a,b)的实现.作为a和b的函数,您的程序的预期运行时间是多少？随机(a,b)结果的概率应该是纯粹均匀分布的,如随机(0,1)

对于Random函数,结果是a和b之间的整数,包括在内.例如,Random(0,1)生成0或1; 随机(a,b)生成a,a + 1,a + 2,...,b

我的解决方案是这样的:

for i = 1 to b-a
    r = a + Random(0,1)
return r

运行时间为T = ba

它是否正确？我的解决方案的结果是否均匀分布？

谢谢

如果我的新解决方案如下所示:

r = a
for i = 1 to b - a //including b-a
    r += Random(0,1)
return r

如果不正确,为什么r + = Random(0,1)使r不均匀分布？

Answer 1

其他人解释了为什么你的解决方案不起作用.这是正确的解决方案:

1)找到最小的数字p,这样2^p > b-a.

2)执行以下算法:

r=0
for i = 1 to p
    r = 2*r + Random(0,1)

3)如果r大于b-a,请转到步骤2.

4)你的结果是 r+a

那么让我们试试随机(1,3).
所以b-a是2.
2^1 = 2所以p必须是2因此2^p大于2.
所以我们将循环两次.让我们尝试所有可能的输出:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1.
01 -> r=1, 1 is not > 2, so we output 1+1 or 2.
10 -> r=2, 2 is not > 2, so we output 2+1 or 3.
11 -> r=3, 3 is > 2, so we repeat.

所以1/4的时间,我们输出1. 1/4的时间输出2. 1/4的时间我们输出3.而1/4的时间我们必须再次重复算法.看起来不错.

请注意,如果您必须执行此操作,则可以使用两个优化:

1)如果你经常使用相同的范围,有一个计算p一次的类,所以你不必每次都计算它.

2)许多CPU具有执行步骤1的快速方法,这些方法未在高级语言中公开.例如,x86 CPU具有BSR指令.