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);

int absn = abs(n);

if( absn == 0 )

{

return 1.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;

}

{

result = temp*temp;

}

else

{

result = temp*temp*x;

}

return ( n < 0 )? (1/result) : result;

}