next up previous
Next: Rational numbers Up: Assignment 0: User-defined objects Previous: Assignment 0: User-defined objects

BigIntegers

BigIntegers are built-in objects that can represent arbitrarily-big integers. There is no upper bound except the limitations of memory size and processing speed.

Whenever you work with a built-in class, you should start by printing and reading the documentation of the class:

http://java.sun.com/products/jdk/1.2/docs/api/java/math/BigInteger.html

  1. Start by making a new directory for this project called Factorial. Copy a working version of Hello.java into this directory and rename it Factorial.java.
  2. Edit the file and rename the class Factorial. Compile and run it. Whenever you begin a project, you should start with a working program.
  3. Write a method named factorial that takes an integer parameter and evaluates its factorial. It can be iterative or recursive.
  4. In main, write a loop that prints a table of the integers from 0 to 30 along with their factorials. At some point around 15, you will probably see that the answers are not right any more. The reason is that there is a finite range of values that can be represented with an integer. In order to handle bigger numbers, you have to use an alternate representation. In Java, one option is the BigInteger class. To import this class, add import java.math.BigInteger to the beginning of your program.
  5. There are several ways to create a new BigInteger, but the one I recommend uses valueOf. The following code converts an integer to a BigInteger:

        int x = 17;
        BigInteger big = BigInteger.valueOf (x);
    Type in this code and try out a few simple cases like creating a BigInteger and printing it. Notice that println knows how to print BigIntegers!
  6. Unfortunately, because BigIntegers are not primitive types, we cannot use the usual math operators on them. Instead we have to use object methods like add. In order to add two BigIntegers, you have to invoke add on one of the objects and pass the other as an argument. For example:

        BigInteger small = BigInteger.valueOf (17); 
        BigInteger big = BigInteger.valueOf (1700000000); 
        BigInteger total = small.add (big);
    Try out some of the other methods, like multiply and pow.
  7. Convert factorial so that it performs its calculation using BigIntegers, and then returns the BigInteger as a result. You can leave the parameter alone--it will still be an integer.
  8. Try printing the table again with your modified factorial function. Is it correct up to 30? How high can you make it go? On my machine, I calculated the factorial of all the numbers from 0 to 999, but it took over 2 minutes. The last number, 999!, has 2565 digits.


next up previous
Next: Rational numbers Up: Assignment 0: User-defined objects Previous: Assignment 0: User-defined objects

Allen Downey
Thu Sep 7 11:50:06 EDT 2000