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,


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(x^2)^\frac{n-1}{2},&n \textrm{ odd}\\[0.3em]
(x^2)^\frac{n}{2},&n \textrm{ even}

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!

Submitted by Tom Roelandts on 12 February 2017

Add new comment