Given the base and exponent, how do we implement the pow(base,exp) function efficiently?
For example
pow(2.0,5) = 32
pow(0.4,2) = 0.16
pow(2.0,-2) = 0.25
For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the base with itself for ‘e’ times where e is the exponent.
There is one more efficient way to calculate this value using divide and conquer technique. If we have to calculate an, we can divide the computation into two similar tasks i.e we can calculate an/2 once, and multiplying it with itself gives the required value
an = an/2*an/2
Here is the C++ implementation of the above algorithm. This reduces the number of multiplications required for calculating the power. Observe how different test cases are handled in the program.