How to implement Random(a,b) with only Random(0,1)? [duplicate]

Question

Possible Duplicate:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)

In the book of Introduction to algorithms, there is an excise:

Describe an implementation of the procedure Random(a, b) that only makes calls to Random(0,1). What is the expected running time of your procedure, as a function of a and b? The probability of the result of Random(a,b) should be pure uniformly distributed, as Random(0,1)

For the Random function, the results are integers between a and b, inclusively. For e.g., Random(0,1) generates either 0 or 1; Random(a, b) generates a, a+1, a+2, ..., b

My solution is like this:

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

the running time is T=b-a

Is this correct? Are the results of my solutions uniformly distributed?

Thanks

What if my new solution is like this:

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

If it is not correct, why r += Random(0,1) makes r not uniformly distributed?

Answer 1

No, your solution isn't correct. This sum'll have binomial distribution.

However, you can generate a pure random sequence of 0, 1 and treat it as a binary number.

repeat
  result = a
  steps = ceiling(log(b - a))

  for i = 0 to steps
    result += (2 ^ i) * Random(0, 1)
until result <= b

KennyTM: my bad.