Why 2^31 is not divisible by n?

Question

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt%28int%29 says:

The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2^31 is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2^30+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.

The algorithm:

int bits, val;
do {
    bits = next(31);
    val = bits % n;
} while (bits - val + (n-1) < 0);

The code tests the case where n > 2^30 and bits > n. Then the most significant bit is set and turns the result in the condition into negative one.

I understand that bits is at most 2^31-1 => there is the 50% probability. The bits can be either < 2^30 or between 2^30 and 2^31

---

Anyway,

1. Why 2^31 is not divisible by n?
2. Why is it effective only when both numbers > 2^30?

I guess some binary division magic, an overflow which breaks the uniform distribution?

Thank you!

Answer 1

This is a problem caused any time you want to generate a random number in a smaller range from one in a larger range where the size of the smaller range isn't divisible by the size of the larger.

If you had a random number between 0 and 9 (inclusive) and wanted to change it to one between 0 and 3, if you just did this trivially as n%4, you'd have a 3/10 chance of getting a 0 (0, 4 or 8)%4, but a 2/10 chance of getting a 3 (3 or 7)%4. The simplest way around this here is to just re-generate the random number if it's greater than 7.

The worst case it's talking about is when the size of the smaller range is just over half the size of the larger one, so you'll have to re-generate just over half of the time.