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.

Answer 1

The standard trick is to generate the powers of x in sequence x², x⁴, x⁸, x¹⁶, x³², ... and include those that are needed in the result.

Answer 2

x^n = e^(n*ln x), if i get you right?

Answer 3

Well, you know that x^a+b = x^a x^b 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;
}

Answer 4

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.

Answer 5

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.

Answer 6

The answer above using exp and log requires 2 long PF power series evaluations, which is usually vastly slower the lg(n) method.