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!