Monday, April 12, 2010

uniform random generator

The last interview asked about the random number generator. The problem is that given a uniform random generator which will generate random number from 0 to m-1, you need to come up with a uniform random generator from 0 to n-1 which n > m. I did the normal way as I started the C++, using

number = (rand() % (max - (min - 1))) + min.

However, the modular operation destroy the uniform distribution.
We need to make the distribution untouched. The interviewer told me that any math operation will destroy the distribution. Think about it carefully. I think he was wrong. There is a way to over come it and using arithmetic operations:

number = (rand() * (float(max - min) / RAND_MAX)) + min.

Another reason of not using modular is that in the pseudo random generator, it uses lower bits in the random value. However the reality is the lower bits are less random than higher bits. If you want a uniform distribution, it is not a good idea to use lower bits.

No comments: