algorithm - How to implement Random(a,b) with only Random(0,1)? - Stack Overflow

algorithm - How to implement Random(a,b) with only Random(0,1)? - Stack Overflow

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?

Your solution is not uniformly distributed. As an example the lowest value a can only be "calculated" by the sum of random(0)+random(0)+random(0)+.... however the probability of a value in "the middle" is higher because it can be calculated as 0+0+0+1+1, and 0+0+1+0+1, and 1+1+0+0+0, and so on. Think of it like throwing 2 dices. The probability of getting 2 (1+1) or 12 (6+6) is lower than the probability of getting 7 (1+6,2+5,3+4,4+3,5+2,6+1) (settlers of catan ftw. ;)).
http://stackoverflow.com/questions/8458392/how-to-get-uniformed-random-between-a-b-by-a-known-uniformed-random-function-ra
This solution produces a uniform distribution by producing a uniform distribution over 0..(2^N-1) then discarding the result if it's out of the required range to construct a uniform distribution over a non-power of 2. Your solution constructs a binomial distribution. 

def rand_pow2(bit_count):
    """Return a random number with the given number of bits."""
    result = 0
    for i in xrange(bit_count):
        result = 2 * result + RANDOM(0, 1)
    return result

def random_range(a, b):
    """Return a random integer in the closed interval [a, b]."""
    bit_count = math.ceil(math.log2(b - a + 1))
    while True:
        r = rand_pow2(bit_count)
        if a + r <= b:
            return a + r

1) Find the smallest number, p, such that 2^p > b-a.

2) Perform the following algorithm:

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

3) If r is greater than b-a, go to step 2.

4) Your result is r+a

So let's try Random(1,3).
So b-a is 2.
2^1 = 2, so p will have to be 2 so that 2^p is greater than 2.
So we'll loop two times. Let's try all possible outputs:

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.

So 1/4 of the time, we output 1. 1/4 of the time we output 2. 1/4 of the time we output 3. And 1/4 of the time we have to repeat the algorithm a second time. Looks good.

Note that if you have to do this a lot, two optimizations are handy:

1) If you use the same range a lot, have a class that computes p once so you don't have to compute it each time.

2) Many CPUs have fast ways to perform step 1 that aren't exposed in high-level languages. For example, x86 CPUs have the BSR instruction.
http://blog.csdn.net/brillianteagle/article/details/38470369

 /*
  * new Random().nextInt(2)用来模拟Random(0,1)，注意new
  * Random().nextInt(2)表示生成≥0且＜2的数，即生成0或1
  */
 public static int getRandomNumber(int a, int b) {
  int diff = b - a;
  int p = getP(diff);
  int result = 0;
  for (int i = 1; i <= p; i++) {
   int random = new Random().nextInt(2);
   result = 2 * result + random;
   /* 如果r大于b-a，重复第2）步 */
   if (result > diff) {
    result = 0;
    i = 1;
   }
  }
  return result + a;
 }

 /* 获得最小的p,使得2^p>b-a */
 public static int getP(int diff) {
  for (int i = (int) Math.ceil(Math.log(diff) / Math.log(2));; i++) {
   if ((Math.pow(2, i)) > diff) {
    return i;
   }
  }
 }

Read full article from algorithm - How to implement Random(a,b) with only Random(0,1)? - Stack Overflow