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. Projects posted are only 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 fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.