Exponentiation by Squaring

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!