Why is 2 ^ 31 not divisible by n?

Question

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

The algorithm is a bit complicated. He rejects values ​​that are in an uneven distribution (due to the fact that 2 ^ 31 is not divisible by n). The probability of deviation of a value depends on n. the worst case is n = 2 ^ 30 + 1, for which the probability of deviation is 1/2, and the expected number of iterations until the loop ends is 2.

Algorithm:

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

The code checks the case when n > 2^30 and bits > n . Then the most significant bit is set and turns the result into a negative condition.

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

---

Anyway,

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

I guess some magic of binary division, overflow, which breaks even distribution?

Thanks!

Answer 1

This is a problem caused by the fact that you want to create a random number in a smaller range from one in a larger range, where the size of the smaller range is not divided by the size of the larger.

If you had a random number from 0 to 9 (inclusive) and it was necessary to change it to one between 0 and 3, if you just did it trivially, like n% 4, you will have a 3/10 chance of getting a 0 (0, 4 or 8)% 4, but a 2/10 chance to get 3 (3 or 7)% 4. The easiest way here is to simply regenerate a random number if it is greater than 7.

The worst case scenario is when the size of the smaller range is slightly larger than half the size of the larger, so you will have to regenerate a little more than half the time.

Answer 2

2 ^ 31 is only divided by power or 2. When you check the code, this special case is processed separately without a loop. The description refers to a failure process, and there n is not a power of 2.

Answer 3

Regarding the first question:

As I understand the proposal, he said that uneven distribution occurs when 2 ^ 31 is not divisible by n.

Sorry, but I do not know the second question.