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!

Add new comment

The content of this field is kept private and will not be shown publicly.
Spam avoidance measure, sorry for this.

Restricted HTML

  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.
Submitted on 12 February 2017