In this article, I present the simple idea of *exponentiation by squaring*. This idea saves computation time in determining the value of large integer powers by “splitting” the exponentiation in a clever way into a series of squaring operations. The technique is based on the fact that, for \(n\) *even*,

\[x^n=(x^2)^\frac{n}{2}.\]

For \(n\) *odd* you can simply decrease \(n\) by one and do an extra multiplication by \(x\) outside of the exponent. This leads to the full expression,

\[x^n=\begin{cases}

x(x^2)^\frac{n-1}{2},&n \textrm{ odd}\\[0.3em]

(x^2)^\frac{n}{2},&n \textrm{ even}

\end{cases}.\]

You then apply this *recursively*, meaning that you don’t just compute \(x^2\) and raise that number to the power of \(n/2\), but keep using the same trick again and again.

For example, if \(n=6\), we first get \(x^6=(x^2)^3\). If we define \(y=x^2\) for clarity, we then get \(y^3=y(y^2)^1=(x^2)(x^2)^2\). This means that \(x^6\) can be computed using only three multiplications instead of six; one to compute \(x^2\), one to compute \((x^2)^2\), and a third one to multiply both together. Of course, for a large \(n\) the gains are much bigger.

For simple numbers and small exponents, computing \(x^n\) directly is not a problem, but when a single multiplication takes a lot of time (e.g., for matrices), or when the exponent is large, it can make a big difference.

## Python Code

Below is a small Python program that computes \(x^n\) recursively.

from __future__ import print_function def exponentiation_by_squaring(x, n): if n == 0: return 1 elif n == 1: return x elif n % 2: return x * exponentiation_by_squaring(x * x, (n - 1) // 2) else: return exponentiation_by_squaring(x * x, n // 2) x = 2 n = 20 print(exponentiation_by_squaring(x, n))

Remember this simple trick and keep it in your algorithm toolbox!

## Add new comment