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 2^{10} = 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, 2^{10} can be calculated as follows.

2^{10} = 2^{5} * 2^{5}

2^{5} = 2^{2} * 2^{2}

2^{2} = 2^{1} * 2^{1}

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;

}