Wednesday, December 2, 2009

Ex5.1-2 of introduction to algorithms

A friend asked my idea about the exercise 5.1-2 of introduction to algorithms. Here is the original question:

Question:
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? ( RANDOM(0,1) returns either 0 or 1 with the same probability, and RANDOM(a,b) is supposed to return any number between [a,b] with the same probability.)

First Answer: [wrong]
My initial answer which is obviously wrong is like this:

RANDOM(int a, int b)
{
int rc = a;
for(int i = 0; i < b-a; ++i)
rc += _RANDOM(0,1);
return rc;
}
But thinking it more carefully, it doesn't return every number at the same probability.

Second Answer:
The question is similar to flip coins. Each time we flip a coin, we have the same probability to get either 0 or 1. If we flip the coin for several times, the probability of getting each permutation of 0 and 1 is the same. So, if we can use each permutation to represent a distinct number between a and b, we shall get the desired RANDOM function.
How to represent a number with a serials of 0 and 1s? Binary format!
So, if we run the RANDOM(0,1) for 1+lg(b-a) times and convert the final permutation to a decimal value plus a, that's the value we want. And we need to be careful since b-a might not be exact power of 2, so we need to run RANDOM(0,1) for ceiling of 1+lg(b-a) times. But a serial of 0 and 1 of this length might represent a number exceeds b-a, we can abandon the value and restart RANDOM(a,b) till the number is smaller than b-a.
And the code is:

#include "cmath"
#include "iostream"
#include "ctime"

using namespace std;
int _RANDOM()
{
int r = rand();
return (r%2 == 0);
}

int RANDOM(int a, int b)
{
int rc = 0;
int i = 0;
// compute log2(b-a) via log10(b-a)/log10(2)
int t = ceil(log10((float)b-a)/log10((float)2) + 1);
unsigned int one = 0x1, zero = 0xfffffffe;
srand(time(NULL));
while(i < t)
{
rc = rc << 1;
if(_RANDOM())
rc |= one;
else
rc &= zero;
if(i ==(t - 1)&& rc > (b-a))
{
rc = 0;
i = 0; //restart loop
}
++i;
}
return rc + a;
}

int main(int argc, char** argv)
{
int a, b;
cin >> a >> b;

int r = RANDOM(a, b);
cout << r << endl;
return 0;
}