CPSC 170 Program 3: Big Integers
Due Wed, April 13 2005

Overview

The Java primitive type int uses a 32-bit two's complement representation, which allows it to represent values in the range -231 to 231-1 (-2147483648 to 2147483647). A programmer who needs to represent a larger number might use a long instead; with 64 bits this extends the range to -263 to 263-1 (-9223372036854775808 to 9223372036854775807). But what if the integers in a program can grow larger than that? If this seems unlikely, remember that the number of moves required to solve the 64-disk Towers of Hanoi problem is 264-1, which is out of range even of a Java long. In situations like this it's useful to have a way to represent arbitrarily large integers. Their manipulation will not be nearly as efficient as that of regular integers, but at least it will be possible to work with them in some form.

Your assignment is to write two classes:

The BigInt ADT and Implementation

The BigIntADT interface is given below:
public interface BigIntADT
{
    // Gives the number of digits in the BigInt
    public int length();

    // Returns a BigInt representing the sum of the
    // current BigInt and int2
    public BigIntADT add(BigIntADT int2);

    // Returns a BigInt representing the product of the
    // current BigInt and int2
    public BigIntADT mult(BigIntADT int2);

    // Returns a BigInt representing the the current BigInt
    // raised to the int2 power
    public BigIntADT power(BigIntADT int2);

    // Returns true if the current BigInt is the same as
    // int2, false otherwise
    public boolean equals(BigIntADT int2);

    // Returns a string representation of the current BigInt
    public String toString();

    // Returns an iterator that provides the digits of the current 
    // BigInt, one at a time.
    public Iterator iterator();
}		    
You should write a LinkedBigInt class that uses a linked list to implement this interface. Some helpful advice:

The EvalBigInts Class

This is a program that takes a space delimited postfix expression at the command line, represents the integers in the expression as BigInts, and uses stack evaluation to evaluate the expression. The expression may contain any non-negative integers but should contain only the operators +, *, and e (for exponent, so postfix 2 3 e = 23 = 8). Note that to use * on the command line you have to put it in quotes; otherwise the command line interpreter thinks you mean "all files in this directory" and passes those names in to args (no kidding; try it). So to evaluate 2 3 e 5 6 * + (that is, 23 + 5*6) using this program you would type
  java EvalBigInts 2 3 e 5 6 "*" +
at the command line.

There is code for a stack evaluator in the text; yours will be similar, but your use of bigints will require some modifications.