Optimized Solution of Power function

Write a C function to compute x^n 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^n. Hence,

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

x^n = 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.