1.10 Computing Big Factorials

In the previous section, we learned that 20! is the largest factorial that can fit in a 64-bit integer. But what if you want to compute 50! or 100!? The java.math.BigInteger class represents arbitrarily large integer values and provides methods to perform arithmetic operations on these very large numbers. Example 1-10 uses the BigInteger class to compute factorials of any size. It also includes a simple main( ) method that defines a standalone test program for our factorial( ) method. This test program says, for example, that 50! is the following 65-digit number:

30414093201713378043612608166064768844377641568960512000000000000

Example 1-10 introduces the import statement. This statement must appear at the top of a Java file, before any class is defined (but after the package declaration). It provides a way to tell the compiler what classes you are using in a program. Once a class like java.math.BigInteger has been imported, you no longer have to type its full name; instead you can refer to it simply as BigInteger. You can also import an entire package of classes, as with the line:

import java.util.*

Note that the classes in the java.lang package are automatically imported, as are the classes of the current package, which, in this case, is je3.basics.

Example 1-10 uses the same caching technique Example 1-9 did. However, because there is no upper bound on the number of factorials that can be computed with this class, you can't use a fixed-sized array for the cache. Instead, use the java.util.ArrayList class, which is a utility class that implements an array-like data structure that can grow to be as large as you need it to be. Because an ArrayList is an object rather than an array, you use such methods as size( ), add( ), and get( ) to work with it. By the same token, a BigInteger is an object rather than a primitive value, so you can't simply use the * operator to multiply BigInteger objects. Use the multiply( ) method instead.

Example 1-10. Factorial4.java

package je3.basics; // Import some other classes we'll use in this example. // Once we import a class, we don't have to type its full name. import java.math.BigInteger;  // Import BigInteger from java.math package import java.util.*;  // Import all classes (including ArrayList) from java.util /**  * This version of the program uses arbitrary precision integers, so it does  * not have an upper-bound on the values it can compute.  It uses an ArrayList  * object to cache computed values instead of a fixed-size array.  An ArrayList  * is like an array, but can grow to any size.  The factorial( ) method is  * declared "synchronized" so that it can be safely used in multi-threaded  * programs.  Look up java.math.BigInteger and java.util.ArrayList while   * studying this class.  Prior to Java 1.2, use Vector instead of ArrayList  **/ public class Factorial4 {     protected static ArrayList table = new ArrayList( ); // create cache     static { // Initialize the first element of the cache with !0 = 1.         table.add(BigInteger.valueOf(1));     }     /** The factorial( ) method, using BigIntegers cached in a ArrayList */     public static synchronized BigInteger factorial(int x) {         if (x<0) throw new IllegalArgumentException("x must be non-negative.");         for(int size = table.size( ); size <= x; size++) {             BigInteger lastfact = (BigInteger)table.get(size-1);             BigInteger nextfact = lastfact.multiply(BigInteger.valueOf(size));             table.add(nextfact);         }         return (BigInteger) table.get(x);     }     /**      * A simple main( ) method that we can use as a standalone test program      * for our factorial( ) method.        **/     public static void main(String[  ] args) {         for(int i = 0; i <= 50; i++)             System.out.println(i + "! = " + factorial(i));     } }