CS170 Assign 4

CPSC 170 Program 4: Big Integers
Due Friday, April 11 2008

Overview

The Java primitive type int uses a 32-bit two's complement representation, which allows it to represent values in the range -2³¹ to 2³¹-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 -2⁶³ to 2⁶³-1 (-9223372036854775808 to 9223372036854775807). But what if the integers in a program can grow larger than that? This may seem unlikely to you, but you experienenced numbers this big back in week five of CS120 when you were asked to represent your age in seconds. Even more dramatic - In week eight of cs120, we hit a ceiling with our factorial function 15! (extending from an int to a long gets us up to 20!). 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:

LinkedBigInt -- implements the the BigIntADT below; represents and manipulates arbitrarily large non-negative integers.
EvalBigInts -- takes postfix expressions using only the operations +, *, e (exponent) and ! (factorial) from a file, and evaluates it using a stack and representing the numbers as LinkedBigInts.

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 a BigInt representing the factorial of int
    public BigIntADT  factorial(BigIntADT int)

    // 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:

If you store the digits backwards in the list it will be easier to manipulate your BigInts (e.g., add them). Think about what you do in computing 437 + 28:
- 8+7=15; put down the 5, carry the 1
- 1 (carry) + 3 + 2 = 6
- 4 + 0 = 4
So the answer is 461. Note that it is computed from right to left, and that it may be necessary to deal with a carry at any point (think about 937 + 75). If each integer is stored backwards in a linked list (that is, with the rightmost digit first), in the first example you would have 8-2 and 7-3-4. Although this looks odd, it gives immediate access to just the digits that you need first: 8 and 7.
Once you have figured out addition, multiplication should be easy. Just remember that x * y is just x + x + ... + x (y xs). That is, you can think of multiplication as repeated addition. Start with 0 and add x to it y times, and voila! You've computed x * y.
Once you have figured out multiplication, exponentiation should be easy. Just remember that x^y is just x * x * ... * x (y xs). That is, you can think of exponentiation as repeated multiplication. Start with 1 and multiply by x y times, and voila! You've computed x^y.
Factorial is the same idea yet again - start at 1 and work your way up to x (1 * 2 *.... * x)
The equals method can just compare the corresponding digits of the two bigints. This does assume that there is just one representation for each integer -- in particular, that there are no leading 0s. So 0 should just be 0, never 00 or 000, and 16 should never be 016. Be sure that your initial representations are in this form and that your BigInts stay in this form as you manipulate them.
You'll want to provide 3 constructors for generating BigInts.

The first should be null - this should create a BigInt initialized to 0.
The second should take an int - allowing us to seemlessly translate between ints and BigInt.
The third should take a String value - this can be used to initialize a BigInt that is already too big to be represented as an int. You need to take care to ensure that the string contains only numbers. If the constructor is called with a bad string, it should throw an exception.

The EvalBigInts Class

This is a program reads from a file containing multiple postfix expressions (delimited by a newline). Each postfix expression is itself space delimited. This program should represent 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 = 2³= 8).

Code for a stack evaluator is in the text and last week's lab; yours will be similar, but your use of bigints will require some modifications.

CPSC 170 Program 4: Big Integers Due Friday, April 11 2008

Overview

The BigInt ADT and Implementation

The EvalBigInts Class

CPSC 170 Program 4: Big Integers
Due Friday, April 11 2008