[f]izzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Exponentiation by squaring

Sharing is caring!

This is a rather short post. in which I explain how to we can implement a fast pow function to raise a number $x$ to the power of $n$.

A rather naive approach would be to do the following:

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 $\mathcal{O}(n)$. We can do better than that.

Let us consider an example.

Assume that we want to calculate $x^8$. We can rewrite it as follows:

$x^8 = x \times x \times x \times x \times x \times x \times x \times x$.

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

$x \times x = x^2$

next we can compute

$x^2 \times x^2 = x^4$

and last

$x^4 \times x^4 = x^8$

which gives as a total of $3$ multiplications.

Lets assume that we want to calculate $x^{13}$. We can rewrite it as follows:

$x^{13} = x^8 \times x^4 \times x$.

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

How do we find the numbers $8, 4$ and $1$? Or in other words, how can we find out what powers of 2 make up $13$?
Well that’s what the binary representation of $13$ tells us:

$13_d = 1101_b$

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

Algorithm

1. Set $result = 1$
2. 1101 $\rightarrow$ we have a power of 2 ($2^0$), so we multiply $result$ with $x$: $result = result \times x$
3. Square $x$: $x = x \times x$ $\rightarrow$ $x = x^2$
4. 1101 $\rightarrow$ we don’t have a power of 2 so skip.
5. Square $x$: $x = x \times x$ $\rightarrow$ $x = x^4$
6. 1101 $\rightarrow$ we have a power of 2 ($2^2$), so we multiply $result$ with $x$: $result = result \times x$
7. 1101 $\rightarrow$ we have a power of 2 ($2^3$), so we multiply $result$ with $x$: $result = result \times x$

Code

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 $\mathcal{O}(\log n)$