public class EfficientPower {
/*
* Aim is to find the power of a number
* in an efficient manner.
* Let us denote the exponent by n.
* Time complexity: O(log2(n))
* Space complexity: O(1)
*/
public static void main(String[] args) {
double base = 10;
int exponent = 2;
System.out.println(fastPower(base, exponent)); // 100.0
}
// Method for efficiently calculating power
private static double fastPower(double base, int exponent) {
if (exponent == 0) {
return 1;
}
// If exponent is negative, take reciprocal of base
// and change sign of the exponent.
if (exponent < 0) {
base = 1 / base;
exponent = -exponent;
}
double answer = 1;
// Update answer based on binary
// representation of exponent
while (exponent != 0) {
// If bit is 1, update answer
if (exponent % 2 == 1)
answer = answer * base;
// If bit is 0, move to next bit
base = base * base;
exponent = exponent / 2;
}
return answer;
}
}