Sep 252013
 

Write a C function to compute xn 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:

xn+m = xm * xn

Hence,

xn = xn/2 * xn/2         (If x is even)
xn = x * xn/2 * xn/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.

You can learn more about Dynamic Programming herehere or here

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)