# Best way to do powerOf(int x, int n)?

•
•  |
•

### Question

So given x, and power, n, solve for `X^n`. There's the easy way that's `O(n)`... I can get it down to `O(n/2)`, by doing

``````numSquares = n/2;
numOnes = n%2;
return (numSquares * x * x + numOnes * x);
``````

Now there's a `O(log(n))` solution, does anyone know how to do it? It can be done recursively.

### Solution

Well, you know that xa+b = xa xb so...

``````int pow(int x, unsigned int y)
{
if (y == 0) return 1;
if (y == 1) return x;
int a = y / 2;
int xa = pow(x, a);
if (a + a == y) // y even
return xa * xa;
else
return xa * xa * x;
}
``````

### OTHER TIPS

The mathematical concept that can be exploited is that `x2n+1 = x2n ⋅ x` and `x2n = xn ⋅ xn`.

The usual implementation is something along these lines (cribbed from the wikipedia article):

``````long power(long x, unsigned long n)
{
long result = 1;
while (n > 0) {
/* n is odd, bitwise test */
if (n & 1) {
result *= x;
}
x *= x;
n /= 2;     /* integer division, rounds down */
}
return result;
}
``````

Recursion isn't necessary or (I'd say) particularly desirable, although it can win on obviousness:

``````long power(long x, unsigned long n)
{
if (n == 0) return 1;
long result = power(x, n/2); // x ^ (n/2)
result *= result;            // x ^ (n/2)*2
if (n & 1) result *= x;      // x ^ n
return result;
}
``````

Of course in any version you overflow a long pretty quickly. You can apply the same algorithms to your favourite bigint representation, although any bigint library is going to include an integer power function already.

Both versions of the function above return 1 for `power(0,0)`. You may or may not consider this a bug.

You'll find an explanation here: Fast exponentiation. For some values of n, you can calculate x^n with fewer multiplications than by using the powers of two trick.

The standard trick is to generate the powers of x in sequence x2, x4, x8, x16, x32, ... and include those that are needed in the result.