In this problem you are going to create a library (i.e. class) to solve the problem that in Java, the int data type can only represent integers in the range [-2,147,483,648 . . 2,147,483,647]; this is not big enough for storing, for example, the population of Earth (7.125 billion) or computing factorials for large values of n.

The Java libraries contain a class BigInteger to solve this problem, but we are going to write our own class, BigInt, with only a subset of the functionality of the Java class.

Representation of Big Integers by Arrays of Digits

We will represent our big integers by using arrays of integers, where each array entry (i.e. element of the array) represents an individual digit of a big integer, Example:

public static final SIZE = 20; // a constant in the BigInt class to indicate the // maximum size of a BigInt array .... // use the constant variable SIZE to declare the size of the array public static int A[] = new int[BigInt.SIZE]; 

An integer such as 57431 is represented by an array A containing integers which are in the range [0 9] (i.e., digits) with as many leading zeros as necessary to fill up the entire array, Example:

00000000000000057431 would be presented as 0 1 2 14 15 16 17 18 19 +----------- ------------------------+ A: | 0 | 0 | 0 ....... | 0 | 5 | 7 | 4 | 3 | 1 | +----------- ------------------------+ 

Note that the elements in the array must all be single digits and that the last entry of the array represents the least significant digit of the integer.

The BigInt array that represents the value for 0 will have SIZE-1 leading 0s and the last digit will be a significant digit, not a leading 0.

We will not represent negative integers, but would be interesting for you to think how we could.

We will also declare a special BigInt object NaBI (Not a Big Int) for error checking purposes. This array will consist of a -1 in slot 0, with the remaining values set to 0:

 0 1 2 14 15 16 17 18 19 +----------- ------------------------+ NaBI: |-1 | 0 | 0 ....... | 0 | 0 | 0 | 0 | 0 | 0 | +----------- ------------------------+ 

The Methods of the BigInt Class:

public BigInt() -- Default constructor to create a BigInt of NaBI. public BigInt(int [] ) -- Constructor that creates a BigInt from an Array passed. The array should be checked that it is a valid representation of a BigInt. If not the object should be constructed as NaBI. public BigInt(int n) -- Constructor that convert the integer n into a big integer object; if n < 0, then the object should be constructed as NaBI; note that n won't overflow the array, since it's an int. public BigInt(String s) -- Constructor that Converts the String s into a big integer; if s does not represent a legal big int (i.e., contains a character other than '0' .. '9' or is longer than SIZE characters) object should be constructed as NaBI. public String bigIntToString(BigInt B) -- Return a String representation of the big integer object B (with leading zeros suppressed); if any member of A is NOT a digit (e.g., is negative or > 9) return "NaBI". public int compareTo(BigInt B) -- Compare two big integer objects and return -1, 0, or 1, depending on whether A < B, A == B, or A > B, respectively. public BigInt add(BigInt B) -- Add two big integers and return a new BigInt representing their sum; if the result overflows, i.e., contains more than SIZE digits, return NaBI. public BigInt mul(BigInt B) -- Multiply two big integers and return a new BigInt representing their product; if the result overflows, i.e., contains more than SIZE digits, return NaBI. 

Algorithms

The algorithms for manipulating these big integers are simply adaptations of the rules for addition and comparison of integers. For example:

To add two arrays of digits, we must go from right to left (i.e. least significant to most significant digit) adding the digits and keeping track of the carry:

 carry: 1 0 1 1 -----------------------+ ... 0 | 5 | 7 | 3 | 3 | 9 | equals 57339 -----------------------+ -----------------------+ ... 0 | 0 | 4 | 5 | 9 | 8 | equals 4598 -----------------------+ -----------------------+ sum: ... 0 | 6 | 1 | 9 | 3 | 7 | equals 61937 -----------------------+ 

Note that the addition will result in an overflow (create a number larger than 20 digits) if the sum of the left-most two digits is larger than 10, in which case you should return NaBI.

We encourage you to go through a similar analysis to determine the algorithm for multiplying two big integers.

Completing your Solution

Begin with the template code BigInt.java. To implement your solution complete each method in the template BigInt.java. Note that this template will compile, because dummy return statements were added just for that purpose; you will need to change these when you add your code.

Important guidelines:

Do not alter the signature of the methods or they may fail the automatic test.

You should examine the method stubs and write appropriate code to implement the functionality described above.

Use the method descriptions above as a guide to write a comment block before each of the methods;