Understanding Java Random next Integer with bound algorithm

Question

I'm looking at the way the Java Random library generates an integer given an upper bound, but I don't quite understand the algorithm. In the docs it 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.

But I really don't see how this implementation takes this into account, specifically the while condition in the code. To me it seems that this would (almost) always succeed with 50% success rate. Especially when looking at very low values for bound (which I think is used a lot when imposing a bound). It seems to me like the condition in the while is just checking the sign of bits, so why bother with the line they use?

public int nextInt(int bound) {
   if (bound <= 0)
        throw new IllegalArgumentException("bound must be positive");

      if ((bound & -bound) == bound)  // i.e., bound is a power of 2
        return (int)((bound * (long)next(31)) >> 31);

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

user_5133585 · Answer

Note that bits - val + (bound-1) < 0 is actually checking whether bits - val + (bound-1) overflows. bits is always equal to or greater than val, and bound is always positive, so there is no way for the LHS to be positive under normal circumstances.

We can think of the < 0 as > Integer.MAX_VALUE.

Let's plot a graph of bits - val + (bound - 1). I have made one on desmos here. Let's say bound is 100 (small bound):

The x axis is bits and y axis is bits - val + (bound-1), and I have added lines on both the x and y axes to indicate Integer.MAX_VALUE. Note that bits is bounded by Integer.MAX_VALUE.

At this scale, you can see that bits - val + (bound-1) seems to never overflow. If you zoom a lot, you'll see:

Note that there is a tiny range of values of bits for which bits < Integer.MAX_VALUE, but bits - val + (bound - 1) > Integer.MAX_VALUE.

For b = (1 << 30) + 1, the graph looks like:

Any b that is greater than 1 << 30 overflows. Hence the 1/2 chance of rejecting the bounds as the documentation said.

Understanding Java Random next Integer with bound algorithm

1 Answers