Problem solving with programming: Computing the power of a given number

Problem solving with programming: 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 2¹⁰ = 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¹⁰ can be calculated as follows.

2¹⁰ = 2⁵ * 2⁵

2⁵ = 2² * 2²

2² = 2¹ * 2¹

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.

Read full article from Problem solving with programming: Computing the power of a given number