Numerical computations in C++ – Exponentiation by repeated squaring
April 17, 2011 Leave a comment
Let’s say that we have to compute the power of a number without using the inbuilt pow function. We can compute the answer using the method of repeated squaring.
Firstly, we assume that the exponent is an integer.
For example. let us compute (13.5)^5.
Now, we know that 5 is 101 in binary notation.
Hence, what we need to compute is
We also observe that and that .
From these observations, we can deduce that repeated squaring of and multiplication of the appropriate intermediate results would lead us to the desired answer. (i.e. Compute and take the product of and .)
Here, prior to the repeated squaring, we calculated the binary representation of the given exponent. We need not necessarily do that. We can do the squaring and the computation of the binary representation simultaneously.
Here is a C++ code fragment to illustrate that:-
//function f takes a computes x^e (where e >= 0) and returns a long value.
long f (int x, int e)
int temp = e, rem; //rem stands for remainder.
long answer = 1, term = 1;
while ( temp != 0)
term = term * x;
rem = temp%2;
if (rem == 1)
answer = answer * term;
temp / = 2;
If we assume that all arithmetic operations take O(1) time, then the above function takes O(n) time where n represents the number of bits in the binary representation of the exponent, e.