Showing posts from March, 2015

Bit twiddling in JDK to generate random number

Some time back a friend asked me an algorithm question:
Given an integer random number generator randomN() that can generate random number in the range [0, N), how will you generate random numbers in the range [0, M) where M I used modulo arithmetic to generate the desired random numbers in the range [0, M). And I reasoned out that if N = q*M + r, every number in the range [0, r] has an occurrence probability of (q+1)/N, but the numbers in the range [r+1, M) has an occurrence probability of only q/N.

It is easy to visualize this. See the diagram below:

You can see that we can divide line of length N units (given in green) by lines of length M units (given in black). When N is not exactly divisible by M, in the last part alone we have only r units.

So if we choose a random integer in the line represented in green, and then take a modulo M on the value, all the values except the values in the range [r+1, M) (represented in red) will occur q+1 times. But the values in that interval wil…