Puzzle 64: The Mod Squad

This program generates a histogram of the numbers mod 3. What does it print?

public class Mod {

    public static void main(String[] args) {

        final int MODULUS = 3;

        int[] histogram = new int[MODULUS];



        // Iterate over all ints (Idiom from Puzzle 26)

        int i = Integer.MIN_VALUE;

        do {

            histogram[Math.abs(i) % MODULUS]++;

        } while (i++ != Integer.MAX_VALUE);



        for (int j = 0; j < MODULUS; j++)

            System.out.println(histogram[j] + " ");

    }

}

Solution 64: The Mod Squad

The program initializes the int array histogram with one location for each of the mod 3 values (0, 1, and 2). All three locations are initially 0. Then the program loops the variable i over all 2³² int values, using the idiom introduced in Puzzle 26. Because the integer remainder operator (%) can return a negative value if its first operand is negative, as discussed in Puzzle 1, the program takes the absolute value of i before computing its remainder when divided by 3. Then it increments the array location indexed by this remainder. After the loop finishes, the program prints the contents of the histogram array, whose elements represent the number of int values whose mod 3 values are 0, 1, and 2.

The three numbers printed by the program should be roughly equal to one another, and they should add up to 2³². If you want to know how to figure out their exact values and you're in the mood for a bit of math, read the next two paragraphs. Otherwise, feel free to skip them.

The three numbers printed by the program can't be exactly equal, because they have to add up to 2³², which is not divisible by 3. If you look at the mod 3 values of successive powers of 2, you'll see that they alternate between 1 and 2: 2⁰ mod 3 is 1, 2¹ mod 3 is 2, 2² mod 3 is 1, 2³ mod 3 is 2, and so forth. The mod 3 value of every even power of 2 is 1, and the mod 3 value of every odd power of 2 is 2. Because 2³² mod 3 is 1, one of the three numbers printed by the program will be one greater than the other two, but which one?

The loop takes turns incrementing each of the three array values, so the last value incremented by the loop must be the high one. This is the value representing the mod 3 value of Integer.MAX_VALUE or (2³¹ - 1). Because 2³¹ is an odd power of 2, its mod 3 value is 2, so (2³¹ - 1) mod 3 is 1. The second of the three numbers printed by the program represents the number of int values whose mod 3 value is 1, so we expect this value to be one more that the first and the last.

The program should therefore print floor(2³² / 3) ceil(2³² / 3) floor(2³² / 3), or 1431655765 1431655766 1431655765—after running for a fair amount of time. But does it? No, it throws this exception almost immediately:

Exception in thread "main" ArrayIndexOutOfBoundsException: -2

        at Mod.main(Mod.java:9)

What is going on here?

The problem lies in the program's use of the Math.abs method, which results in erroneous mod 3 values. Consider what happens when i is -2. The program computes the value Math.abs(-2) % 3, which is 2, but the mod 3 value of -2 is 1. This would explain incorrect numerical results, but it leaves us in the dark as to why the program throws an ArrayIndexOutOfBoundsException. This exception indicates that the program is using a negative array index, but surely that is impossible: The array index is calculated by taking the absolute value of i and computing the remainder when this value is divided by 2. Computing the remainder when a nonnegative int is divided by a positive int is guaranteed to produce a nonnegative result [JLS 15.17.3]. Again we ask, What is going on here?

To answer that question, we must go to the documentation for Math.abs. This method is named a bit deceptively. It nearly always returns the absolute value of its argument, but in one case, it does not. The documentation says, "If the argument is equal to the value of Integer.MIN_VALUE, the result is that same value, which is negative." Armed with this knowledge, it is obvious why the program throws an immediate ArrayIndexOutOfBoundsException. The initial value of the loop index i is Integer.MIN_VALUE, which generates an array index of Math.abs(Integer.MIN_VALUE) % 3, which equals Integer.MIN_VALUE % 3, or 2.

To fix the program, we must replace the bogus mod calculation (Math.abs(i) % MODULUS) with one that actually works. If we replace this expression with an invocation of the following method, the program produces the expected output of 1431655765 1431655766 1431655765:

private static int mod(int i, int modulus) {

    int result = i % modulus;

    return result < 0 ? result + modulus : result;

}

The lesson of this puzzle is that Math.abs is not guaranteed to return a nonnegative result. If its argument is Integer.MIN_VALUE—or Long.MIN_VALUE for the long version of the method—it returns its argument. The method is not doing this just to be ornery; this behavior stems from the asymmetry of two's-complement arithmetic, which is discussed in more detail in Puzzle 33. Briefly, there is no int value that represents the negation of Integer.MIN_VALUE and no long value that represents the negation of Long.MIN_VALUE. For library designers, it might have been preferable if Math.abs threw IllegalArgumentException when it was passed Integer.MIN_VALUE or Long.MIN_VALUE. One could, however, argue that the actual behavior is more consistent with Java's built-in integer arithmetic operations, all of which overflow silently.