Homework 4: Arithmetic Overload (100 pts, due Monday, February 23rd by 11:59pm)

For this homework assignment, you will write a library to enable arithmetic using big numbers -- up to 100 digits long. In the process, you will have to write a class with heavy use of operator overloading, a feature particular to C++.

Part 1: BigInt

Download and view the file bigint.hpp. It is the header file for the class you will have to write. Write the accompanying bigint.cpp file, implementing all of the member functions listed in the header file. We have provided the output operator for you so that you can print integers to the screen, in case you need to debug your code. We have also provided a Makefile that will compile your code. Here are some pointers to help you along the way:

• It is nowhere near as bad as it looks. Think of how to implement one function in terms of another. For example, it is easiest to write + in terms of +=. Of all the comparison functions, you really only need two; the rest are defined in terms of the two you write.
• Your code with use the digits array to store the digits of the stored number. Use grade-school arithmetic algorithms to do the dirty work. Make sure that each element in the array really holds a number between 0 and 9; use the negative member variable to deal with negative numbers.
• Many times throughout your code, you will need to refer to the object you are working in. The way to do this is *this. (As you might guess, * and this have meanings on their own, but you'll use them together every time for this assigment.) For example, here is my code for operator++:

void BigInt::operator++()
{
  *this += 1;
}

• The operator+() (the unary + operation) really does nothing. It is defined only as a counterpoint to unary -, which negates. Note that applying + to a negative number still does nothing. (Contrast to applying - to a negative number, which makes it positive.)
• C++ allows ++ (and --) to appear before or after the variable in question. To distinguish these cases to an overloader, the prefix form uses operator++() and the postfix form uses operator++(int). The int parameter in the postfix form is irrelevant -- it is used solely to differentiate prefix from postfix.
• operator long() is a conversion operator that implements casting to long. Because their return value is not obvious on inspection, we don't write the return values separately, even though, say, operator long() does indeed return a long.
• The conversion should return 0 if the value of the BigInt being converted is out of range. Search online to find how to get the maximum long.
• For the arithmetic operations, there is the chance for overflow and/or underflow. Do not worry about these cases, but do make sure that your code will not access the digits array outside of its bounds. (This is somewhat tricky in the multiplication operation.)
• Remember that 0 and -0 are the same number.
• The intent is for you not to modify bigint.hpp. All of your code should be in bigint.cpp

Part 2: Testing

We have provided a sample test program (main.cpp) that implements a few simple tests on the BigInt class. You should add additional tests to ensure that your code works as intended. Your tests must cover every operator at least once, and you should think about ways that combinations of arguments can cause problems. (For example, does your subtraction algorithm deal with a larger number subtracted from a smaller?) There is no standard testing library for C++, so you will have to work without a unit-testing framework. The breadth of the tests is a graded part of this assignment. We will, of course, test your BigInt implementation with our own unit tests.

Challenge (5 extra-credit points)

The design above for BigInt is very wasteful of space -- each element in the digits array takes up 4 bytes (on most systems) but holds a number only between 0 and 9. Instead, update your implementation to use unsigned ints and use their full range of 0 to 4294967295. This is trickier than it seems; you will have a hard time testing if you should carry during addition when your underlying addition overflows internally.

If you complete this challenge, submit both the original, digit-based implementation and your enhanced one.

Deliverables

• bigint.hpp (you probably haven't changed it, but submitting it makes grading easier)
• bigint.cpp
• main.cpp (modified with your tests)
• Your Makefile (not required, but highly recommended)
• (Optionally) Your bigint.hpp/.cpp for the challenge problem.