Lab 9 -- BigNums

In this lab we will implement BigNums -- unlimited precision integers. A calculator program is provided to you. Your job is to use the Java collection classes to implement an integer type that allows values with any number of digits. This permits multiplication or addition of very large integers, and the factorial operation for numbers much larger than would be allowed by standard implementation. For example, Java's 32-bit integers allow the computation of !12 (12-factorial). Our BigNum calculator will compute !100, or !1000, or even larger numbers if you patience allows. Click here to download the jar file for this lab.

Part 0: Structures.

We will implement BigNums as lists of digits. Since most of the arithmetic operations require us to move from the low-order digits (the one's place) to higher-order digts (tens or hundreds or thousands or whatever), we will store values starting with the low-order and proceding to higher-order digits. For example, the number 123,456,789,012 will be stored as

start->2->1->0->9->8->7->6->5->4->3->2->1->end

Consider the way we convert a standard integer to a BigNum. We can generate the digits with a loop that repeatedly looks at the digit x%10 and reduces x to x/10. For example, if we start with x= 123 this generates the values

x = 123
x%10 = 3;    x = x/10 = 12
x%10 = 2;    x = x/10 = 1
x%10 = 1;    x = x/10 = 0

For the way we will store BigNums, we will convert the int 123 to the BigNum 123 by constructing a new LinkedList, then successively adding the digit 3, then 2, then 1. Here is code that will do this, taken from one of the BigNum constructors. This constructor, of course, has already created the new LinkedList, which is called "number".

// This converts x, which must be >= 0, to a BigNum.
public BigNum(int x) {
     do {
          number.add(new Integer(x % 10));
          x = x/10;
     } while (x > 0);
}

Printing a BigNum involves iterating through the digits stored in the list and printing them. We need to print the digits starting with the highest order and ending with the lowest order: we print the number 123 by first printing 1, then 2, then 3, though the digits are stored as

start -> 3 -> 2 -> 1 -> end

There is an easy way to accomplish this. Rather than the usual iterator we will use a ListIterator, which can move either way along the list: it has methods next() and previous(). One of the constructors for ListIterator allows us to specify an index on which to start the iterator. We will specify the end of the list, by giving this constructor the list size as its index. Other than this, we use the usual code for iterating through the entries of a list. Again, "number" is the name of the variable that holds the LinkedList:

// prints the BigNum
public void print() {
     ListIterator digits = number.listIterator(number.size() );
     while (digits.hasPrevious() ) {
          Integer i = (Integer) digits.previous();
          System.out.print(i.intValue());
     }
     System.out.println();
}

Part 1: The jar file
If you save and expand the jar file you will find the following files:

• BigNum.java   This has the BigNum implementation, including headers for the methods you need to write. This is the only file you need to change for this lab.
  
• Calc.java    This implements a calculator that uses BigNums. It includes the main() method for this lab. You should not need to change this file. In case you are interested, this file implements a recursive-descent parser and interpreter for the context-free grammer that describes the calculator language:
       E -> E+F | F
       F -> F*G | G
       G -> !G | (G) | number
  If you take a course in Compilers you will learn to write and implement such grammars.
  For our purposes you only need to know that the language of the calculator you will implement allows expressions that make use of 3 operators: +, *, and !, as well as parentheses. Note that ! is the "factorial" operator; !n is the product of the first n integers: 1*2*3*4*5....*n.  Note also that we write the ! before the argument; you may have seen this written as n! in Math books, but we will write it as !n.
  
• IntCalc.java   This is a stand-alone program that implements an integer calculator. This does everything your calculator will do, but it is restricted to 32-bit integers -- values up to about 2 billion. You might want to see how large a factorial you can compute with this calculator, and what happens if you exceed this value.
  
• SimpleInput.java   This is the simple input class we have used all semester. All it does is read lines of text in as Strings; the rest of the parsing is handled within the Calc class.

Part 2: Factorials

The easiest step in implementing BigNums is to handle the factorial operation, so we will start there. To compute !n you need two methods. The first, which we call factorial(), consists of a loop that multiplies a fixed BigNum by 2, by 3, and so forth, up to multiplying by n. The second method handles these individual multiplication steps. Note that these require us to multiply a BigNum by a single integer. We call this method scalarTimes().

A. The scalarTimes() method.

You need to implement the method

public BigNum scalarTimes( int n)

Here is the algorithm. We consider the digits of the current BigNum one at a time, starting at the lowest order digit. We keep an integer variable called "carry" that starts out at 0. We construct a new, empty BigNum in which to put the result. For each digit of the current BigNum we multiply the digit times n and add the carry. This total % 10 is the next digit for the result BigNum; this total / 10 becomes the next carry. When we have reached the end of the current BigNum we still have to deal with any remaining carry. In a final loop we repeatedly add the digit carry%10 to the result BigNum, and replace carry by carry/10. This continues until the carry reaches 0.

For example, suppose we want to multiply the BigNum 456 times the integer 12.
Step 1: carry = 0; 12*6+carry = 72. The first digit is 2; the new carry is 7.
Step 2: carry = 7; 12*5+carry = 67. The next digit is 7; the new carry is 6.
Step 3: carry = 6; 12*4+carry = 54. The next digit is 4; the new carry is 5.
Step 4: carry = 5; the BigNum is exhausted. The next digit is 5; the new carry is 0.
The answer is 5472. Check it out.

B. The factorial method.

You need to implement the method

public BigNum factorial(int n)

This computes !n and returns the result as a BigNum. You want to start with a result BigNum with the value 1. There is a constructor for BigNums that takes an integer argument and converts this argument to a BigNum. For the rest, just do a scalarTimes of this result with all the integers between 2 and n, and return the result.

At this point you should be able to test your factorial method by compiling the BigNum.java file and running the Calc program. The factorial operator should work, though you can't combine factorials in more complex expressions.

Part 3. Addition

You need to implement the method

Public BigNum add( BigNum x)

This adds x to the current BigNum. You can do this essentially the same way you would do it by hand. Start with the low-order digit of each number. As long as there are digits add the two digits and the carry together. The total %10 becomes the next digit of the result; the total/10 becomes the new carry. When one of the BigNums runs out of digits add carries and the remaining digits of the other BigNum. When both BigNums are empty continue separating the carry into digits and adding them to the result until the carry is exhausted.

Again, you can check out your implementation by compiling the BigNum.java file and running the Calc program. You should be able to correctly add numbers of arbitrary length.

Part 4. Multiplication

You need to implement the method

Public BigNum times(BigNum x)

This multiples the current BigNum by x. Again, do this the same way you would do it by hand. Start with the low-order digit of x, and keep an integer variable "shiftCount" that start with 0. At each step you do a scalarTimes of the current BigNum with the next digit of x, and add to the low-order end "shiftCount" zeroes. Add this onto the result. Contine with all of the digits of x, and return the result.

For example, suppose the current BigNum is 3456 and we want to compute times(789).
Step 1: result is 0. scalarTimes of 3456 times 9 is 31104. We shift no 0's. The result is 31104.
Step 2: result is 31104. scalarTimes of 3456 times 8 is 27648. Shift one 0 to get 276480.
        Add 276480 to result to get 307584.
Step 3: result is 307584. scalarTimes of 3456 times 7 is 24192. Shift two 0's to get 2419200.
        Add 2419200 to result to get 2726784.
The answer is 2726784. Check it out.

There you have it. Your calculator is now complete.