## (20 points)

As usual you can work in pairs.

### Concepts

• 2's complement arithmetic
• Text-base UI

### Problem

In the world of computing, there is a need to be able to store very large integers. One example where this need shows up is with RSA encryption, where the code needs to work with numbers with several hundred didits.  The given integral primitives of Java (int and long) are not big enough.  To meet this need, you will design a BigInt class to hold these very large numbers and manipulate them.

### Specification

Implementation:
Your BigInt class will store signed integers.  The class must provide the following methods:

 BigInt(String val) Construct a BigInt object and initialize it with the integer represented by the String.  Throw an appropriate exception (BigIntFormatException) if the string does not represent a signed integer (i.e. contains illegal characters) BigInt(BigInt val) This is the copy constructor. It should make a deep copy of val. Making a deep copy is not strictly necessary since as designed a BigInt is immutable, but it is good practice. BigInt(long val) Construct a BigInt object and intitialize it wth the value stored in val BigInt add(BigInt val) Returns a BigInt whose value is (this + val) BigInt multiply(BigInt val) Returns a BigInt whose value is (this * val) BigInt subtract(BigInt val) Returns a BigInt whose value is (this - val) BigInt factorial() Returns a BigInt whose value is this! int compareTo(Object) Have the BigInt class implement the Comparable interface. boolean equals(Object) Override the equals() method from Object. String toString() Returns the decimal representation of this BigInt as a String String toString2s() Returns the 2's complement representation of this BigInt as a String using the minimum number of digits necessary (e.g. 0 is "0", -1 is "1", 2 is "010", -2 is "10", etc).

In order to store the digits, use a doubly-linked list structure; this means a Node holds a reference to the Node before it and the Node after it.  The data to be stored in each Node is one (binary) digit of the number. It is important to use a double-linked list because different algorithms need to move in different directions through the data. Don't create a separate LinkedList class that is a copy of what we did in class. Instead, create a Node inner class, and all needed instance fields (such as Node head, etc.) in BigInt.

You are required to store the number in the linked list using the 2's complement representation. A good introduction to 2's complement arithmetic is given on Wikipedia. You must decide which end of this linked list structure is the least-significant digit. Of course, you are free to store other features of the BigInt such as its number of digits.

User Interface:
This is going to be a text-based program where the user can input the 4 arithmetic operations (+, -, *, !).  Once the program runs, it will print a small prompt to the user and then wait for user input (use the Scanner class).  The program will then parse the input, perform the operation, and display the result.  The user will type h to get a small help description and q to quit.  Here is a sample run.  User input is in red:

Enter here> 5 + 10
15
Enter here> -4 * 22
-88
Enter here> 5!
120
Enter here> q

As we've learned in MVC, this control of the user interface belongs in a separate class.  Make sure to include a main method so that the program can be run from the command line.

The input should be parsed correctly even if the user does not use any spaces (such as 5+10). Your program should handle input errors, such as an incorrect operator or a bad number, with helpful error messages. Your program should not throw any exceptions.

### Documentation, Style & Testing

1. Make sure you have documented your public interfaces well.  Remember, you are building these classes from scratch.  No one has any idea of what they do except you.  You need to communicate these ideas to the reader.
2. Use appropriate style that we've discussed in class.  This includes (but not limited to) named constants, private methods, and throwing exceptions when appropriate.
3. Test your program with the given unit test file. Don't forget to turn in this file as well as your other files.