# Exponentiation by squaring

This is a rather short post. in which I explain how to we can implement a fast `pow`

function to raise a number to the power of .

A rather naive approach would be to do the following:

1 2 3 4 5 6 7 8 9 10 |
int pow(int x, int n){ int result = 1; while (n > 0){ result *= x; n--; } return result; } |

This is ok, but the algorithm has a running time of . We can do better than that.

Let us consider an example.

Assume that we want to calculate . We can rewrite it as follows:

.

which requires multiplications. What we can do to reduce the number of multiplications is to first compute:

next we can compute

and last

which gives as a total of multiplications.

Lets assume that we want to calculate . We can rewrite it as follows:

.

with and being all powers of 2. The great thing about and being a power of 2 is that we can easily get them by squaring (see previous example).

How do we find the numbers and ? Or in other words, how can we find out what powers of 2 make up ?

Well that’s what the binary representation of tells us:

Now that we have our powers of 2, all we need to do is to keep squaring (that is compute , then , etc) and every time we reach a power of two (‘1’ in binary representation) we multiply the intermediate results. So in order to compute we iterate over the binary representation of from the least significant bit (right-most bit) to left-most and perform our squaring and multiplication.

**Algorithm**

- Set
- 110
**1**we have a power of 2 (), so we multiply with : - Square :
- 11
**0**1 we don’t have a power of 2 so skip. - Square :
- 1
**1**01 we have a power of 2 (), so we multiply with : **1**101 we have a power of 2 (), so we multiply with :

**Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 |
int pow(int x, int n) { int result = 1; while (n > 0) { if ((n & 1) == 1) { result = result * x; } x = x * x; n = n >> 1; } return result; } |

The running time thus becomes