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)); } }
Get Java Examples in a Nutshell, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.