Binary Exponentiation

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