# Find power of a number

Looking for optimization, smart tips and verification of complexity: O (log (base 2) power).

NOTE: System.out.println("Expected 16, Actual: " + Power.pow(2, 7)); is a typo. It correctly returns 128.

/**
* Find power of a number.
*
* Complexity: O (log (base 2) power)
*/
public final class Power {

private Power() { }

/**
* Finds the power of the input number.
* @param x     the number whose power needs to be found
* @param pow   the power
* @return      the value of the number raised to the power.
*/
public static double pow(double x, int pow) {
if (x == 0) return 1;
return pow > 0 ? getPositivePower(x, pow) : 1 / getPositivePower(x,  -pow);
}

private static double getPositivePower(double x, int pow) {
assert x != 0;
if (pow == 0) return 1;

int currentPow = 1;
double value = x;
while (currentPow <= pow/2) {
value = value * value;
currentPow = currentPow * 2;
}

return value * getPositivePower(x, pow - currentPow);
}

public static void main(String[] args) {
System.out.println("Expected 6.25, Actual: " + Power.pow(2.5, 2));
System.out.println("Expected 16, Actual: " + Power.pow(2, 7));
System.out.println("Expected 0.25, Actual: " + Power.pow(2, -2));
System.out.println("Expected -27, Actual: " + Power.pow(-3, 3));
}
}

-
I assume you don't want to use the built-in java.lang.Math.pow function. –  ChrisW Jan 14 '14 at 0:27

This can get worse than O(log pow). [Remark: in O notation, the base of the logarithm is irrelevant, since it represents only a multiplication with the constant]

Let pow be 2n-1 for some n. Then you're computing powers

1, 2, 4,..., 2^{n-1},
(now called for pow = (2^n-1) - 2^{n-1} = 2^{n-1} - 1)
1, 2, 4,..., 2^{n-2},
(now called for pow = (2^{n-1}-1) - 2^{n-2} = 2^{n-2} - 1)
1, 2, 4,..., 2^{n-3},
...


All in all,

n + (n-1) + ... + 1 = n(n+1)/2


calls of inner loop. In terms of pow, this is O(log2 pow).

Instead, observe pow as a binary number. I don't do Java, so I'll just sketch this in C, which is quite like it.

double px = x; // current power of x
double result = 1;
while (pow > 0) {
if (pow % 2) result *= px;
pow /= 2;
px *= px;
}


So, you are observing x, x2, x4, x8,... and multiplying with them if the corresponding binary digit of pow is equal to 1. This has O(log pow) steps.

By the way, I don't think 27 is expected to be 16. ;-)

-

Bug #1: 0.0n where n > 0 is equal to 0.0, and not 1 as you have in your code if (x == 0) return 1; (although 00 is 1, not 0, and 0.0n where n < 0 is NaN).

Bug #2: You very carefully have the test method:

System.out.println("Expected 16, Actual: " + Power.pow(2, 7));


But, 27 is actually 128.

At this point, I figure a vote-to-close, but, FYI:

Picking apart the core method getPositivePower(double, int) .... This is your code:

private static double getPositivePower(double x, int pow) {
assert x != 0;
if (pow == 0) return 1;

int currentPow = 1;
double value = x;
while (currentPow <= pow/2) {
value = value * value;
currentPow = currentPow * 2;
}

return value * getPositivePower(x, pow - currentPow);
}

• Why do you need the assert? Sure, you can check the input value is correct, but, there is only one place to call the method, and it is a few lines above. There is no reason to assert everything.... you have to trust something somewhere, and in my opinion, this is overly cautious.
• in the last line, you are either 1, or 0 powers short of your intended result, so why do you have to do a full recursion? Simply: `return value * (pow == currentPow ? 1 : x);
-