[ Team LiB ] Previous Section Next Section

1.9 Caching Factorials

Example 1-9 shows a refinement to our previous factorial examples. Factorials are ideal candidates for caching because they are slightly time consuming to compute, and more importantly, there are few factorials you actually can compute, due to the limitations of the long data type. So, in this example, once a factorial is computed, its value is stored for future use.

Besides introducing the technique of caching, this example demonstrates several new things. First, it declares static fields within the Factorial3 class:

static long[  ] table = new long[21];
static int last = 0;

A static field is kind of like a variable, but it retains its value between invocations of the factorial( ) method. This means that static fields can cache values computed in one invocation for use by the next invocation.

Second, this example shows how to create an array:

static long[  ] table = new long[21];

The first half of this line (before the = sign) declares the static field table to be an array of long values. The second half of the line actually creates an array of 21 long values using the new operator.

Finally, this example demonstrates how to throw an exception:

throw new IllegalArgumentException("Overflow; x is too large.");

An exception is a kind of Java object; it is created with the new keyword, just as the array was. When a program throws an exception object with the throw statement, it indicates that some sort of unexpected circumstance or error has arisen. When an exception is thrown, program control transfers to the nearest containing catch clause of a try/catch statement. This clause should contain code to handle the exceptional condition. If an exception is never caught, the program terminates with an error.

Example 1-9 throws an exception to notify the calling procedure that the argument it passed is too big or too small. The argument is too big if it is greater than 20, since we can't compute factorials beyond 20!. The argument is too small if it is less than 0, as factorial is only defined for nonnegative integers. Examples later in the chapter demonstrate how to catch and handle exceptions.

Example 1-9. Factorial3.java
package je3.basics;

/**
 * This class computes factorials and caches the results in a table for reuse.
 * 20! is as high as we can go using the long data type, so check the argument
 * passed and "throw an exception" if it is too big or too small.
 **/
public class Factorial3 {
    // Create an array to cache values 0! through 20!.
    static long[  ] table = new long[21];
    // A "static initializer": initialize the first value in the array
    static { table[0] = 1; }  // factorial of 0 is 1.
    // Remember the highest initialized value in the array
    static int last = 0;

    public static long factorial(int x) throws IllegalArgumentException {
        // Check if x is too big or too small.  Throw an exception if so.
        if (x >= table.length)   // ".length" returns length of any array
            throw new IllegalArgumentException("Overflow; x is too large.");
        if (x<0) throw new IllegalArgumentException("x must be non-negative.");

        // Compute and cache any values that are not yet cached.
        while(last < x) {
            table[last + 1] = table[last] * (last + 1);
            last++;
        }
        // Now return the cached factorial of x.
        return table[x];
    }
}
    [ Team LiB ] Previous Section Next Section