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