A better solution for my approach to create procedure Rand(a,b), using procedure Rand(0,1)

Question

I have been reading CLRS and encountered the problem to write a procedure Rand(a,b) which generates a random number between a to b uniformly at random, using a procedure Rand(0,1) which generates 0 or 1 with 50% probability.

I have thought of the following solution, which is O(b) in time:

int Rand_a_b(int a,int b)
{
    int i,k=0;
    for(i=0;i<b-a;i++)
    {
         k+=Rand(0,1);
    }
    return a+k;
}

Please suggest a better approach to this.

Answer 1

If the number of distinct numbers in the range is not a power of two, you have to be careful, because any procedure which always takes N numbers sees only 2^N different possibilities, and it will not be possible to distribute 2^N different possibilities evenly over a range if the range does not have a power of two different possibilities.

One approach when generating numbers between a..b is to use k random numbers as individual bits in a k-bit number to produce a number in the range a..a+2^k-1, where k is chosen so that a+2^k-1 >= b. If it turns out that the random number you have produced is out of range, start again from scratch. This dodges the problem above by taking a variable number of random bits, depending on whether and how often you generate something out of range and have to start again.

Answer 2

here is an algorithm: calculate the difference between a and b: k = abs(a-b) and start doing a binary search like so:

keep a number n = 0.flip your coin - Rand(0,1), if the outcome is 1 add k/2 to your n else add nothing. than flip it again for k/4 and repeat until k/i is 0.

Answer 3

That here should make it in log(n). (I didn't check for boundaries, its not tested!) You can't make it faster that that - if you emit only one bit a time, you need at least log(b-a) rounds for an interval.

function Rand_a_b(int a, int b) {
   if (a == b) return a;
   int middle = (b-a)/2;
   if (Rand(0,1)) {
      return Rand_a_b(middle + 1, b);
   } else {
      return Rand_a_b(a, middle);
   }
}