Search code examples
calgorithmrandombig-oclrs

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

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.

Solution

  • 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.