Pingala's binary exponentiation algorithm — ~200 BCE, for counting Sanskrit metres

# Pingala's binary exponentiation algorithm — ~200 BCE, for counting Sanskrit metres

In a Sanskrit treatise on prosody written around 200 BCE, the mathematician Pingala gives a recipe for counting how many distinct metrical patterns are possible in a verse of $n$ syllables. The recipe is four short aphorisms:

> "(Place) two when halved" > > "When unity is subtracted then (place) zero" > > "Multiply by two when zero" > > "Square when halved" > > — *Chandahsūtra* 8.28–31 (~200 BCE), trans. Datta & Singh (1938)

Read as instructions to a clerk with a writing slate, these four lines describe an iterative procedure that computes $2^n$ — the number of possible long/short syllable arrangements in a metre of $n$ syllables. Read as a modern algorithm, they describe **exponentiation-by-squaring**: the technique every modern computer uses to compute large powers efficiently, and the technique that makes RSA and Diffie-Hellman feasible.

The recurrence Pingala wrote down in 200 BCE is the same recurrence running inside every TLS handshake on the modern internet.

The algorithm, in modern notation

To compute $2^n$ using Pingala's four rules:

1. Write down $n$. 2. If $n$ is even, halve it. Record a *halve* step. 3. If $n$ is odd, subtract 1. Record a *subtract* step. 4. Repeat until you reach 1. 5. Now reverse the trace and compute, starting from 2: - For each *halve* step, **square** the running value. - For each *subtract* step, **multiply by 2**.

Example for $n = 6$ (a Gayatri metre):

| Step | Action | Running value | Record | |---|---|---|---| | Start | — | 6 | — | | 1 | halve | 3 | halve | | 2 | subtract 1 | 2 | subtract | | 3 | halve | 1 | halve |

Now reverse the trace and compute upward, starting from 2:

| Step | Trace bit | Operation | Result | |---|---|---|---| | Start | — | — | $2$ | | 1 | halve | square | $2^2 = 4$ | | 2 | subtract | × 2 | $4 \times 2 = 8$ | | 3 | halve | square | $8^2 = 64$ |

Result: $2^6 = 64$. There are 64 possible long/short syllable arrangements in a six-syllable Gayatri metre.

The trace itself — *halve, subtract, halve* — is the binary representation of $n$ in reverse: $6 = 110_2$, read bit-by-bit. The algorithm is **base-2 positional arithmetic applied to exponentiation**, written down ~1,900 years before Leibniz's formalization of binary number theory.

Why this matters

In a naive implementation, computing $2^{64}$ requires 64 multiplications: $2 \times 2 \times 2 \times \ldots$. Pingala's algorithm requires only $\lceil \log_2 64 \rceil = 6$ steps. For $2^{1024}$ (the size of a typical RSA key exponent), naive multiplication requires 1,024 operations; the squaring algorithm requires 10. The speedup is the difference between cryptography being feasible and cryptography being computationally hopeless.

The modern name for this technique is **exponentiation by squaring**, or "binary exponentiation." It appears in every introductory algorithms textbook (Cormen et al., *Algorithms*, ch. 31) as the canonical example of $O(\log n)$ arithmetic. Every public-key cryptographic primitive — RSA, Diffie-Hellman, elliptic curve cryptography, every TLS session — depends on it.

Pingala didn't know any of that. He was trying to count metrical patterns in poetry.

What Pingala was actually doing

The *Chandahsūtra* is a Sanskrit treatise on prosody — the study of metre in Vedic and classical verse. Sanskrit metres are sequences of syllables, each classified as **long** ($g$, *guru*) or **short** ($l$, *laghu*). A metre of $n$ syllables has $2^n$ possible arrangements of longs and shorts. Pingala's algorithm answers: *how many arrangements are possible?*

This is a deeply practical question for a prosodist. Sanskrit poetics distinguishes specific named metres (Gayatri, Tristubh, Jagati, Anustubh) by their syllable count and pattern. Knowing the *total number* of possible patterns lets the prosodist enumerate them, classify them, and analyze which subset are metrically permissible.

Pingala's algorithm is one of several combinatorial tools in the *Chandahsūtra*. The text also includes the **meru-prastāra** — a table of binomial coefficients $\binom{n}{k}$ that counts how many arrangements have exactly $k$ long syllables. This table was later extended by Halayudha (~10th c. CE) in his commentary, ~700 years before Pascal's triangle reaches Europe via Tartaglia (1556) and Pascal (1654).

The Halayudha commentary

Pingala's text is terse to the point of cryptic. The four aphorisms are, in the original Sanskrit, about 12 words total. They presuppose a working knowledge of the algorithmic procedure they describe.

The standard mathematical reading comes from **Halayudha**, a 10th-century commentator whose *Mṛtasañjīvanī* unpacks Pingala's aphorisms with worked examples and proof sketches. Halayudha's commentary is what lets modern Sanskritists confidently reconstruct the algorithm; without it, the aphorisms could be read several ways.

That a 10th-c. mathematician needed to write a commentary clarifying a 2nd-c.-BCE algorithm is a hint that the underlying technique was oral-tradition material older than Pingala's written codification. Pingala is the surviving canonical text; the algorithm he records is likely centuries older still in the Sanskrit prosody tradition.

Comparison with Leibniz (1703)

Gottfried Wilhelm Leibniz publishes the *Explication de l'Arithmétique Binaire* in 1703 — the European founding text of binary number theory. Leibniz formalizes positional base-2 notation: every integer expressible as $\sum b_i \cdot 2^i$ where $b_i \in \{0, 1\}$.

Pingala's algorithm operates on exactly this representation, but **embedded in a prosody manual rather than a treatise on number**. Pingala doesn't generalize to addition, subtraction, or multiplication in base 2. He gives the specific algorithm for the specific problem of computing $2^n$.

The honest framing: **Pingala did not invent binary arithmetic**. He gave a recursive algorithm whose internal logic operates on the binary decomposition of $n$. The algorithm and the general number system are different things; the algorithm is older.

There is no surviving evidence of textual transmission from Indian prosody to Leibniz. Leibniz did correspond with Jesuit missionaries in China and knew about the *I Ching*'s 64 hexagrams (a base-2 system); his interest in binary had multiple roots. Pingala's *Chandahsūtra* was not among them as far as the historical record shows.

What this leaves us with

A Sanskrit prosody manual from ~200 BCE contains a recursive algorithm that, run on modern hardware, would be recognized immediately as **exponentiation by squaring** — the foundational technique of public- key cryptography. The four aphorisms are doing arithmetic on the binary representation of an integer, ~1,900 years before binary representation was a thing European mathematics had a name for.

Pingala wasn't trying to discover anything about numbers. He was trying to count poems. The algorithm fell out of the counting problem, recorded in four short lines in a manual for prosodists, and sat in the Sanskrit textual tradition for two millennia before modern computer science gave it a name.

---

Sources

- [Datta & Singh, *History of Hindu Mathematics: A Source Book* (1938)](https://archive.org/details/wg143) — pp. 75-77, Pingala's algorithm with translated aphorisms. - Plofker, K. (2009). *Mathematics in India*. Princeton University Press, ch. 3. — the *Chandahsūtra* in the Sanskrit prosody tradition. - Knuth, D. (1997). *The Art of Computer Programming*, vol. 2, §4.6.3. — modern treatment of exponentiation by squaring; cites Pingala in historical notes. - Leibniz, G.W. (1703). *Explication de l'Arithmétique Binaire*. — the European founding text on binary.

Related claims

- [Baudhāyana's √2 approximation](/c/25102086-4a59-542f-a510-57fe7b2e355a) — earlier Sanskrit (Sulbasutras, ~800 BCE), iterative-refinement algorithm with similar resemblance to a later European method (Newton-Raphson).