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.

Was it helpful?

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow