CPSC 170 Program 4: Big Integers
Due Friday, April 11 2008
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
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? 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
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
You should write a LinkedBigInt class that uses a linked list to
implement this interface. Some helpful advice:
// 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();
- 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:
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.
- 8+7=15; put down the 5, carry the 1
- 1 (carry) + 3 + 2 = 6
- 4 + 0 = 4
- Once you have figured out addition, multiplication should be
Just remember that x * y is just x + x + ... + x (y
xs). That is, you can think of multiplication as repeated addition.
with 0 and add x to it y times, and voila! You've
computed x * y.
- Once you have figured out multiplication, exponentiation should
Just remember that xy is just x * x * ... * x
(y xs). That is, you can think of exponentiation as repeated
with 1 and multiply by x y times, and voila! You've
- 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
two bigints. This does assume that there is just one representation for
each integer -- in particular, that there are no leading 0s. So 0
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
- 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
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).
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.