CSC 143
Homework # 5
A REALLY Big Integer

(20 points)

As usual you can work in pairs.

Concepts

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.
  4. Carefully test your code and include information about the testing you performed in your report.  

Written Report

You must turn in a short report that discusses your program, describes the class design, and discusses issues you encountered while working on it.   Your report should cover the following:
  1. How many digits can an int in Java hold?  How many digits can a long in Java hold?
  2. Planning: This assignment didn't require much in the way of class design, but did require a lot of algorithm design.  How did you go about coming up with your solution?
  3. Implementation: Describe your algorithm for multiplying two BigInts.  Is this the same algorithm you would follow if you had to do the math with paper and pencil?  If not, why did you choose this aglorithm?  Is it more or less efficient than the paper/pencil version?
  4. Testing: How did you test your code?  What sort of bugs did you encounter?  Are there any unresolved problems in the code?  Be sure to list any ways in which the program falls short of the specification.
  5. Evaluate this project.  What did you learn from it?  Was it worth the effort?  This could include things you learned about specifications and interfaces, design issues, Java language issues, debugging, etc.


Good Luck!