Friday, April 25, 2014

Computing the power of a given number

Given a base and it's exponent, how do we efficiently evaluate it?
In other way, how do implement a pow() function which is typically provided by a library.

For example 210 = 1024.

The simplest method that comes to our mind is multiply the base with 1 in a loop for exponent times.

double result = 1;
for( i = 0; i < exp; i++ )
{
    result = result*base;
}

This method runs in O(n) time complexity where n is the exponent. 

We can make this efficient by using Divide and Conquer technique. Considering the above example, 210 can be calculated as follows.

210 = 25 * 25
25 = 22 * 22
22 = 21 * 21

In each step we avoid computing half of the product which can save us time.
Here is the C++ function to calculate the result. In this function I have handled negative exponents also. This method runs in O( log n) complexity.

  double pow(double x, int n) 
  {
        int absn = abs(n);

        if( absn == 0 )
        {
            return 1.0;
        }

        else if( absn == 1)
        {
            return (n < 0) ? (1/x) : x;
        }
       
        double temp = pow(x, absn/2);
        double result;
        
        if( absn % 2 == 0 )
        {
            result = temp*temp;
        }
        else
        {
           result = temp*temp*x;
        }
        return ( n < 0 )? (1/result) : result;
  }