*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:

But thinking it more carefully, it doesn't return every number at 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;

}

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;

}

## 2 comments:

Why we just don't use simply the following formula?

(10 ^ floor(log(a))) * RANDOM(0,1) + a

Looking forward

Post a Comment