# 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 $\operatorname{O}(\log \verb~pow~)$. [Remark: in $\operatorname{O}$-notation, the base of an logarithm is irrelevant, since it represents only a multiplication with a constant]

Let $\verb~pow~ = 2^n - 1$ for some $n$. Then you're computing the following powers:

• $1, 2, 4,\dots, 2^{n-1}$, followed by a function call for $\verb~pow~ = (2^n-1) - 2^{n-1} = 2^{n-1} - 1$;

• $1, 2, 4,\dots, 2^{n-2}$, followed by a function call for $\verb~pow~ = (2^{n-1}-1) - 2^{n-2} = 2^{n-2} - 1$;

• $1, 2, 4,\dots, 2^{n-3}$, followed by a function call for $\verb~pow~ = (2^{n-2}-1) - 2^{n-3} = 2^{n-3} - 1$;
...

All in all, $n + (n-1) + ... + 1 = n(n+1)/2$ calls of the inner loop. In terms of pow, this is $\operatorname{O}(\log^2 \verb~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, x^2, x^4, x^8,...$ and multiplying with them if the corresponding binary digit of pow is equal to $1$. This has $\operatorname{O}(\log \verb~pow~)$ steps.

By the way, I don't think $2^7$ is expected to be $16$. ;-)

• I added some MathJax to this answer (the edit's in the queue right now) but I'm unsure how you want MathJax for that big code block starting with 1, 2, 4,..., 2^{n-1}. Can you edit it the way you want to do it? – haykam Aug 3 '16 at 3:14
• @Peanut Thank you. I've TeXified it now (that was not an option when I first wrote the answer). Feel free to suggest further improvements if you think I did something wrong or unclear. – Vedran Šego Aug 3 '16 at 13:13

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);