1 Problem statement

Naive way to exponentiate a number, say 315, is to calculate the following: see image.

This will take 14 multiplications. It is possible to get the same result with less multiplications using binary method. Binary method uses the fact that any exponent could be represented using a sum of powers of two. For example, for 15 we have:

15 = 2^3 + 2^2 + 2^1 + 2^0 = 8 + 4 + 2 + 1

So to nd 3^15 we can do

3^15 = 3^8 ×3^4 ×3^2 ×3^1

which would take 6 multiplications: 3 multiplications to nd (and reuse later) 3^8,3^4,3^2 and 3 more to multiply the numbers to get the final result.

2 Implementation

Implement the class Exponentiation.java.

public class Exponentiation {

public int binaryMultiplicationCount(int exponent) {
// calculate number of multiplications needed to find x^exponent using binary method. Note
// that the number of multiplications is independent of x and as a
// result x is not passed as an argument.

}

public double binaryExponentiation(double x, int exponent) {
// Calculate x^exponent using binary method.
}
}

3 Sample input-output

Create the le Driver.java whose modied version will be used for grading.

3.1 Input

public class Driver {

public static void main(String[] args) {
Exponentiation exp = new Exponentiation();
double base = 3;
int exponent = 15;
double result = exp.binaryExponentiation(base, exponent);
double correctResult = Math.pow(base, exponent);
int numberOfMultiplications = exp.binaryMultiplicationCount(exponent);
System.out.println("Result: " + result + " (Correct result = " + correctResult + ")");
System.out.println("Number of multiplications needed: " + numberOfMultiplications);
}
}

3.2 Output

Result: 1.4348907E7 (Correct result = 1.4348907E7)
Number of multiplications needed: 6
Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.