Compute x^n (x to the power n)

Write a function to compute xⁿ which uses minimum number of multiplications.

unsigned int power(double x, unsigned int n)

Brute Force Solution: O(n) time

The brute force method for this is to use a for loop

double power(double x, unsigned int n)
{
    double product = 1;
    for(int i=0; i<n; i++)
    {
        product = product * x;
    }
    return product;
}

We can also write the function recursively. But recursion gives no advantage in terms of performance. In fact it is always less optimal than non-recursive version.

double power(double x, unsigned int n)
{
    if (n == 0)
        return 1;
    return x * power(x, n-1);
}

Time Complexity: O(n) Space Complexity: For non-recursive version its O(1), for recursive version its O(n).

Optimized Solution: O(lg(n)) time

A Better Solution is to do Exponentiation by squaring. In this method we take advantage of the basic formula:

x^n+m = x^m * xⁿ

Hence,

xⁿ = x^n/2 * x^n/2         (If x is even) xⁿ = x * x^n/2 * x^n/2   (If x is odd)

double power(double x, unsigned int n)
{
    if( n == 0)
        return 1;
    double retValue = 1;
    while(n)
    {
        if(n%2)
             retValue = retValue * x;
        x = x * x;
        n = n/2;
    }
   return retValue;
}

The recursive version of above code will be something like:

double power(double x, unsigned int n)
{
    if( n == 0)
        return 1;
    double temp = power(x, n/2);
    if (n%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

Note that the above code is not same as the below code (though both are recursive and both does exponential multiplication)

unsigned int power(double x, unsigned int n)

{
    if (n == 0)
        return 1;
    if(x%2 == 0)
        return power(x, n/2) * power(x, n/2);
    else
        return x * power(x, n/2) * power(x, n/2);
}

In the above code we are calling power method twice and hence it will be much more time consuming. (if n=10) then power(x,5) will be called twice.

Its a typical problem with recursion. The approach in the first recursive function is that call power(x,5) once and store its value in a variable (temp) and for second time use that value.

This approach is called Dynamic Programming.