Introduction
The goal of this project was to write a C++ class that will hold and perform operations on an arbitrary precision integer value. The expected output goal was to calculate and print the 20th Mersenne Prime using either a vector or deque for the internal storage. In addition computing the 30th Mersenne Prime was presented as a challenge. A key decision I made in this project was to store my internal value in ascending order, as opposed to descending, to make several calculations easier to implement.
Details
Calculation Functions
The first part of the project involved implementing several template functions outside the Integer class that performed several operations on containers. The operations were shift left, shift right, add, subtract, multiply and divide. All of these functions took input iterators to the beginning and end of the arguments and an output iterator to the beginning of the output container as arguments. In the place of the second input container the shift left and shift right functions took an int value corresponding to the amount of places to shift.
- Shift Operators
The shift functions were very simple and simply padded the output container in the case of shift left or ran through part of the input container before writing in the case of shift right.
- Add/Subtract
Both the add and subtract method involved reading through the containers and performing the correct operation on the digits. This involved keeping a carry value that might affect the next operation.
- Multiply
Multiply was somewhat more complex. Since normal multiplication requires quite a large number of operations I put in a multiplication table. This table held the values corresponding to the first input container times the digits 0 -9 for each row of the table. Then as I progressed down the second input container I just added values from the table corresponding to the digit in the second container and shifting it as necessary.
- Division
Division was also very complex. My implementation involves repeated subtraction of the bottom value from the top and adding 1 to a counter until the top value is less then the bottom value.
Integer
- Storage and Constructor
I stored the integer value of Integer in a container, either vector or deque, that had random access. In addition I held the value in reverse digit order, i.e. in ascending order (ones, tens, hundreds, etc.). Also I kept track of the sign of the Integer as a bool, true is positive and false is negative.
- I implemented two constructors. The first took an int value and read it into the storage container. The second took a string value and read it into the container. However, this constructor also had to check that the values put into the container were valid digits and not other characters.
- Operators
The operators were implemented as friend functions so that they could be called with the . operator, and instead use lhs op rhs.
- Comparison
The comparison operators were implemented using calls to ==, <= and < which were implemented to run through containers and compare their values.
- Other Operators
The other operators were implemented by calling the corresponding op= operator which is implemented in the Integer class.
- Output
The output operator << was implemented using an ostream lhs and Integer rhs. It involved reading from the back of the container and outputting the value to lhs.
- Implemented Operators
All of the operators called the corresponding functions defined earlier in the program. The calls inside Integer created a storage container which was of sufficient size to hold the largest possible result for the given size of Integers. Then the corresponding function was called. A few comments are needed for a couple of the more odd operations.
- Abs
Abs computed the absolute value of the Integer, by simply changing the sign.
- Negation
Negation computed the negative of the Integer, by switching the sign
- Modulus
The mod operator was rather tricky to implement and ended up being quite an expensive operation. It first makes a call to divide to get the division value. Then it multiplies by the given divisor to get a multiple value. Then the multiple is subtracted from the dividend to get the modulus. Due to the size of the project this operation was not fully optimized.
- Pow
Pow computed the value of a given Integer raised to an int exponent. It used a helper function that allows the exponentiation to occur in log n time.