Fast exponentiation
- Due Nov 4, 2019 by 10pm
- Points 0
- Submitting a file upload
- File Types cpp and h
Description
For this lab, we're going to add one new method to our BigInteger class. The method will be used to support exponentiation by using the method of fast exponentiation. The method signature will look like
BigInteger BigInteger::operator^(const BigInteger& other) const;
and should return the value of the current object raised to the power of the the object passed in as a parameter (other).
Tests First
Before writing the code, you should add new tests to your unit testing framework to check that your code is working. For this assignment, you can assume the value of the exponent is non-negative. Check with your TA or me to ensure you have a good set of tests. I would recommend using bc to help you compute some large of the results that are hard to compute. In bc, the exponentiation operator is ^.
Fast Exponentiation
The algorithm for fast exponentiation is to recursively compute xy by noticing that xy = xy/2*xy/2. We can compute xy/2 once and multiply it by itself to get the final answer. Be sure to account for when y is odd (xy=x*xy/2*xy/2). Since this is a recursive solution, we also have to identify the base case: x0=1. With this, you can write the full solution.
As a helpful hint, I would encourage you to write a similar function with the signature of
BigInteger BigInteger::operator^(int exponent) const;
and debug your algorithm with this simpler code first. Once you have this working, you can move on to using an exponent that is also a BigInteger.
Checking for odd/even
You should probably create a new private helper function that you can use to check if a BigInteger is odd or even. An example signature would be
bool BigInteger::isEven() const;
and would return true for even numbers and false for odd numbers. Typically, to test for evenness of an integer, we can use a simple line of code:
x % 2 == 0
but that doesn't work because we haven't defined the modulus operator for our BigInteger class. Fortunately, we don't have to support a robust modulus operator to check if a number is even. We can simply look at the least significant digit and test if it is even! As a result, testing for evenness for our BigInteger class can be done quite quickly and succinctly.
Dividing y by 2
You will also probably want to build a second private helper function that divides the exponent in half. An example signature for this would be
BigInteger BigInteger::half() const;
For the same reason that we build isEven(), we'll need to build this half method: we don't support a general purpose division operator for our BigInteger. Again, dividing by 2 is much simpler than dividing by any arbitrary value; we can do this from most significant digit to least significant digit. We can divide the current digit by 2 and store the result for the given digit. Also, we need to keep track of the remainder of the division so that we can use it for the next digit. If the remainder is 1, we need to incorporate that into the division for our next digit.