EXCURSION 1 Effective Java Programming Language Guide by Joshua Bloch

Excursion 1: Random Thoughts

Effective Java Item 30 ("Know and use the libraries") begins with a broken random number generation idiom (page 145):

    private static Random rnd = new Random();

    // Common but flawed!
    static int random(int n) {
        return Math.abs(rnd.nextInt()) % n;
    } 

The item goes on to note that if this method is invoked repeatedly with n = 2 * (Integer.MAX_VALUE / 3), two thirds of the numbers generated fall in the lower half of the range. Occasionally I get e-mail asking "Why does the random method do this?" Now it can be told!

Suppose you you like three flavors of ice cream equally well, say vanilla, chocolate, and strawberry. You want to choose a flavor at random by flipping coins. Unfortunately, there's no way to do this in any finite number of coin flips. If you flip a coin n times, there are 2ⁿ possible outcomes, which isn't divisible by three. To make this concrete, consider the following naive algorithm:

1. Flip the coin twice. There are four possible outcomes: TT, TH, HT, HH, or expressed as binary numbers, 00, 01, 10, 11. Call the binary number resulting from the two coin flips outcome.



2. Since we're trying to choose among three flavors, take outcome mod 3. If the result is 0, choose vanilla; if 1, choose chocolate; if 2, choose strawberry.

Of course this doesn't work. You'll end up choosing vanilla twice as often as either of the other flavors, as two of the four possible outcomes (TT and HH) result in vanilla.

It turns out that the broken idiom above uses essentially the same algorithm! It flips 31 "coins" (the bits of Math.abs(rnd.nextInt())), generating an outcome between 0 and 2³¹ - 1. Then it chooses among 2 * (Integer.MAX_VALUE / 3), or (2/3) * (2³¹ - 1) "flavors" (or results) using the % operator, which is essentially the same as the mod operator.

The number of results (or modulus), (2/3) * (2³¹ - 1), was chosen carefully so that there are 3/2 as many possible outcomes as there are results. Each outcome is assigned to one result, which means that not all results have the same number of outcomes assigned to them: Every number in the first half of the range gets two outcomes assigned to it, but every number in the second half of the range gets only one.

To make this concrete, here's how it looks with a 4-bit random number and a modulus of (2/3) * (2⁴ - 1), or 10:

	Entire Range										Half of Range
Outcomes	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15
Result	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5

The picture for a 31-bit word and a modulus of (2/3) * (2³¹ - 1) looks the same, only much, much larger. As you can see, there's room for one and one half copies of the result set on the outcome set, so the lower half of the possible outcomes have two choices assigned to them. That's why the method puts two thirds of the numbers it generates in the lower half of its range.

So how do you fix the problem? Let's go back to the ice cream example. While you can't choose fairly from among three flavors in any finite number of coin tosses, you can choose fairly if you're willing to tolerate the possibility of arbitrarily many coin tosses. Here is a simple algorithm that works:

1. Flip the coin twice. If the result is HH, throw it out and repeat the process. Eventually, you'll get a result that's not HH.



2. If the result is TT, choose vanilla; if TH, choose chocolate; if HT, choose strawberry.

This is a probabilistic, potentially nonterminating algorithm that terminates with probability 1. The expected number of times that you'll have to do step 1 is 1 + 1/4 + 1/4² + 1/4³ ... = 1.33, which isn't too bad.

Believe it or not, this is essentially the algorithm that Random.nextInt(int) implements. Here's the actual code, which is a bit tricky:

    public int nextInt(int n) {
        if (n <= 0)
            throw new IllegalArgumentException(n + " is not positive");

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

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

The if statement after the validity check solves an unrelated problem with the idiom: The low order bits of numbers returned by linear congruential pseudorandom number generators such as the one implemented by Random.nextInt() have a short period. In other words, the sequence formed by successive values of the low order bits repeats itself far more often than it should. The if statement after the validity check has the effect of returning the correct number of high order bits (instead of low order bits) if the modulus (n) is a power of two.

The do-while loop implements exactly the "revised ice cream choosing algorithm" shown above. It generates a random outcome between 0 and 2³¹ - 1 and then checks to see if the outcome falls in a "partial copy" of the range implied by the modulus. If it does, the value is rejected and the procedure repeated until an acceptable value is generated. The probability of a value being rejected depends on n. The worst case occurs when n = 2³⁰ + 1, for which the probability of a reject is 1/2. Under these circumstances the expected number of iterations before the loop terminates is 2, which is entirely acceptable.

Another bit of cleverness in this code is the loop termination test,

     while (bits - val + (n - 1) < 0);

Finally, note that the nextInt(int) method computes outcomes using Random.next(31), rather than Math.abs(rnd.nextInt()) (as in the broken idiom above). This corrects the "catastrophic flaw" noted in the book: If you use the latter expression, you will, on very rare occasion, get a negative result, as Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE. The former expression avoids negative numbers entirely: Random.next(31) returns a uniformly distributed random non-negative integer.

To reiterate the main point of Item 30, the code for Random.nextInt(int) is not, in all likelihood, something that a typical application programmer would come up with on his own. This tiny method is the result of a couple of days of hard work by yours truly in consultation with John Rose and Guy Steele. It was subsequently reviewed by other experts and then battle-tested for years by millions of users. By using the standard library method, you take advantage of the knowledge of those who wrote it and the experience of the many who used it before you.