Numerical computations in C++ – Exponentiation by repeated squaring

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 13.5^4 \times 13.5^0 \times 13.5^1

We also observe that 13.5^4 = (13.5^2)^2 and that 13.5^2 = (13.5^1)^2.

From these observations, we can deduce that repeated squaring of 13.5 and multiplication of the appropriate intermediate results would lead us to the desired answer. (i.e. Compute 13.5^1, 13.5^2, 13.5^4 and take the product of 13.5^1 and 13.5^4.)

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;

}

return answer;

}

——–

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.

———

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: