Hoarding programming problems for you!

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:

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

The running time thus becomes \mathcal{O}(\log n)