# just do IT

## 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.)

`RANDOM(int a, int b){int rc = a;for(int i = 0; i < b-a; ++i)rc += _RANDOM(0,1);return rc;}`
`#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;} `