← All writing Ancient algorithms, 15 min read

Pingala's binary: Sanskrit meters, the meru prastara and Pascal's triangle, in Python

Pingala's Chandahshastra lists every pattern of heavy and light syllables and numbers each one, which reads as binary. The sutras, the meru prastara and Python.

A line of 4 syllables, each heavy or light, can take 16 rhythms. Pingala (Piṅgala), in the Chandaḥśāstra, his Sanskrit treatise on poetic meter, lists every such pattern in 15 closing rules and gives each one a number. Write a heavy syllable as 0 and a light one as 1, read the pattern from right to left, and Pingala's number for it is that binary number plus 1.

The same rules count the patterns by halving, which is the square-and-multiply method for powers. Halayudha, a 10th-century commentator, reads the last rule as the triangle now called Pascal's triangle. My text is an 1874 edition that prints his commentary; I worked his examples and turned the rules into tested Python (pingala.py on GitHub), as part of Ancient algorithms, implemented.

The problem: how many rhythms can a line have?

Sanskrit meter counts syllables by weight. A syllable is light (laghu, written l) if it has a short vowel and no consonant cluster after it, and heavy (guru, written g) otherwise. The letters g and l are Pingala's own shorthand.

A meter of fixed length, say 4 syllables per line, allows a fixed set of weight patterns: gggg, lggg, glgg and so on. A prosodist wants to answer 4 questions about them:

  1. List them all in a fixed order (prastāra, "spreading out").
  2. Given a row number, find the pattern without writing out the list (naṣṭa, "the lost one").
  3. Given a pattern, find its row number (uddiṣṭa, "the one pointed out").
  4. Count them (saṅkhyā, "number"), and count how many have a given number of light syllables (lagakriyā, "the l-g operation").

Pingala's 15 sutras answer the first 3 questions and give the total count. The count by number of light syllables rests on Halayudha's reading of the last sutra, which is disputed. Halayudha's commentary says to work them with numbers written bhūmau, on the ground.

Who was Pingala, and when did he write?

  • Pingala, author of the Chandaḥśāstra (also called the Chandaḥsūtra), 8 chapters on Vedic and classical meters. The combinatorial rules are the end of chapter 8. His date is debated. Jayant Shah gives the 2nd century BCE, and David Mumford's review of Kim Plofker's Mathematics in India reports "perhaps" the 3rd century BCE. A later tradition, reported by the commentator Ṣaḍguruśiṣya and cited by Parmanand Singh, makes Pingala the younger brother of the grammarian Panini, which would make him earlier.
  • Halayudha (Halāyudha), author of the Mṛtasañjīvanī, the commentary printed with the sutras in the 1874 edition. Shah dates it c. 950 CE, and Singh places Halayudha in the 10th century. Every procedure below follows his reading.

I used the Bibliotheca Indica edition by Viśvanātha Śāstrī (Calcutta, 1874), on archive.org, reading the sutras on pages 231 to 237 from the page images.

The sutras of chapter 8

The 15 sutras below are 8.20 to 8.34 in the 1874 edition. The 2001 edition Amba Kulkarni uses numbers the last 2 as 8.34 and 8.35.1

द्विकौ ग्लौ ॥ २० ॥ मिश्रौ च ॥ २१ ॥ पृथग्ला मिश्राः ॥ २२ ॥ वसवस्त्रिकाः ॥ २३ ॥
लर्धे ॥ २४ ॥ सैके ग् ॥ २५ ॥
प्रतिलोमगुणं द्विर्लाद्यम् ॥ २६ ॥ ततोऽप्येकं जह्यात् ॥ २७ ॥
द्विरर्धे ॥ २८ ॥ रूपे शून्यम् ॥ २९ ॥ द्विः शून्ये ॥ ३० ॥ तावदर्धे तद्गुणितम् ॥ ३१ ॥
द्विर्द्व्यूनं तदन्तानाम् ॥ ३२ ॥ परेण पूर्णम् ॥ ३३ ॥ परे पूर्णमिति ॥ ३४ ॥

dvikau glau || 20 || miśrau ca || 21 || pṛthag lā miśrāḥ || 22 || vasavas trikāḥ || 23 ||
l ardhe || 24 || saike g || 25 ||
pratilomaguṇaṃ dvir lādyam || 26 || tato 'py ekaṃ jahyāt || 27 ||
dvir ardhe || 28 || rūpe śūnyam || 29 || dviḥ śūnye || 30 || tāvad ardhe tadguṇitam || 31 ||
dvir dvyūnaṃ tadantānām || 32 || pareṇa pūrṇam || 33 || pare pūrṇam iti || 34 ||

Word by word

SutraSanskritPartsMeaning
20dvikau glaudvika + g + lg and l, as a pair
21miśrau camiśra, "mixed" + caand the 2 mixed
22pṛthag lā miśrāḥpṛthak + l + miśraseparately, the l's mixed
23vasavas trikāḥvasu + trikathe Vasus (a word for 8) are the triplets
24l ardhel + ardha, "half"l, at a halving
25saike gsa + eka + gwith 1 added, g
26pratilomaguṇaṃ dvir lādyampratiloma + guṇa, dviḥ, l + ādyamultiplied in reverse order, twice, starting from l
27tato 'py ekaṃ jahyāttataḥ + api, eka, hāthen also one should take away 1
28dvir ardhedviḥ + ardha2, at a halving
29rūpe śūnyamrūpa, "a unit" + śūnya, "empty"when 1 is taken, an empty mark
30dviḥ śūnyedviḥ + śūnyatwice, at an empty mark
31tāvad ardhe tadguṇitamtāvat + ardha + tad + guṇitaat a halving, that much multiplied by itself
32dvir dvyūnaṃ tadantānāmdviḥ + dvi-ūna + tad-antatwice, less 2: of all those ending there
33pareṇa pūrṇampara + pūrṇaby the next, full
34pare pūrṇam itipara + pūrṇa + itifor the next, full, and so on

My translation, following Halayudha

20 to 23. Write g and l. Write that pair twice, mixed: g after the first copy, l after the second. For each further syllable, write the list so far twice and add g's to the first copy and l's to the second.

24 and 25. To find the pattern at a row number: if the number is even, halve it and write l. If it is odd, add 1, halve, and write g.

26 and 27. To find the row number of a pattern: start at the last l with 1, and moving right to left, double at each syllable. At a g, take 1 away after doubling.

28 to 31. To count the patterns of n syllables: if n is even, halve it and mark 2. If it is odd, take 1 away and mark 0. Then from the last mark back, starting with 1, double at each 0 and square at each 2.

32 and 33. Double the count and take away 2 to get the total of all lengths up to n. Double it in full to get the count for n + 1.

34. Build the meru: a top cell with 1, then rows of 2, 3, 4 cells below, each cell straddling 2 above. Fill the end cells with 1 and every other cell with the sum of the 2 cells above it, and so on for as many rows as you want.

The sutras do not say where to start counting, what number to write first, or that the 2 and the 0 are written as marks. Halayudha supplies all of that. On sutra 23 he adds that the 8 triplets are the gaṇas beginning with ma, the 3-syllable feet named at the start of the text. In the list they come out in the order ma, ya, ra, sa, ta, ja, bha, na.

What the sutras leave open

The rules for the pattern-to-number direction (26 and 27) say "in reverse order" and "starting from l", without saying which l. Halayudha takes the last l and moves left. That choice is forced if the procedure is to undo sutras 24 and 25. The meaning of the last sutra is the larger open question, covered under "What is debated".

Worked example: Halayudha's 6-syllable meter

Halayudha works each rule on the 6-syllable meter, the gāyatrī. The examples below are his, and the code reproduces each one.

The lost pattern (sutras 24 and 25). Which pattern is 6th in the list of 6-syllable patterns?

NumberEven or oddWriteNext number
6evenl6 ÷ 2 = 3
3oddg(3 + 1) ÷ 2 = 2
2evenl2 ÷ 2 = 1
1oddg(1 + 1) ÷ 2 = 1
1oddg1
1oddg1

The 6th pattern is lglggg. Halayudha's commentary gives the same steps: halving 6 gives an l, then 3 is odd and gives a g, then 2 gives an l, and from there "saike g" repeats until 6 syllables are written.

The pointed-out pattern (sutras 26 and 27). Now go back. In lglggg the last l is in place 3. Start there with 1:

  • place 3, l: double, 2;
  • place 2, g: double and take 1 away, 3;
  • place 1, l: double, 6.

The row is 6.

The count (sutras 28 to 31). How many 6-syllable patterns are there?

  • 6 is even: halve to 3, mark 2.
  • 3 is odd: take 1 away to get 2, mark 0.
  • 2 is even: halve to 1, mark 2.
  • 1 is odd: take 1 away to get 0, mark 0.

The column of marks reads 2, 0, 2, 0. From the bottom: start at 1, double for the 0 to get 2, square for the 2 to get 4, double for the 0 to get 8, square for the 2 to get 64. Halayudha gets 64 and then lists the counts for the longer named meters: 128, 256, 512, 1,024, 2,048 and 4,096 for 7 to 12 syllables.

The total (sutra 32). Double 64 and take 2 away: 126 patterns of 1 to 6 syllables, which is 2 + 4 + 8 + 16 + 32 + 64.

Why it works, and where the binary is

Sutras 20 to 23 build the list recursively. The list for n syllables is the list for n - 1 syllables with g added, followed by the same list with l added. So the 3-syllable list is:

RowPatternRead right to left, g = 0, l = 1ValueGaṇa
1ggg0000ma
2lgg0011ya
3glg0102ra
4llg0113sa
5ggl1004ta
6lgl1015ja
7gll1106bha
8lll1117na

The first syllable alternates g, l, g, l down the list, the second in pairs, the third in fours. That is binary counting with the lowest digit on the left, and both search rules follow from it.

Nashta. The first syllable is g in odd rows and l in even rows. Rows 2k - 1 and 2k differ only in their first syllable, and what is left of both is row k of the list 1 syllable shorter. So: if the row is even, write l and halve; if odd, write g, add 1 and halve. Each step peels the lowest binary digit off row - 1.

Uddishta. Run nashta backwards. If the first syllable is l, the row is twice the row of the rest. If it is g, it is twice the row of the rest, less 1:

r(l p)=2 r(p),r(g p)=2 r(p)−1r(\texttt{l}\,p) = 2\,r(p), \qquad r(\texttt{g}\,p) = 2\,r(p) - 1

Start from the empty pattern with row 1 and add syllables from the right. A trailing g gives 2 × 1 - 1 = 1, so trailing g's change nothing. That is why Pingala can say "start from the l": the first l from the right is where the number starts to grow.

Sankhya. The count for n syllables is 2^n. If n is even, 2^n = (2^(n/2))^2, so halve and later square. If n is odd, 2^n = 2 × 2^(n-1), so take 1 away and later double. The marks record which case applied at each step, and reading them back from the bottom rebuilds the power. This is exponentiation by repeated squaring. Amba Kulkarni (2017) points out that it is the method Knuth calls the binary method for powers. It takes about 2 log2(n) steps where doubling n times takes n: for n = 64 the code writes 7 marks, and for n = 1,000 it writes 15.

Meru. An n-syllable pattern with k light syllables is either an (n - 1)-syllable pattern with k light syllables followed by g, or one with k - 1 light syllables followed by l. So the count obeys

(nk)=(n−1k)+(n−1k−1)\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}

and each cell of the triangle is the sum of the 2 cells above it.

The meru prastara

Halayudha's commentary on sutra 34 describes the construction. My translation of the core of it, from pages 236 and 237 of the 1874 edition:

Draw 1 square cell at the top. Below it draw 2 cells, each sticking out halfway on either side; below those, 3; below those, 4; as far as you want. Write 1 in the first cell. In the row of 2 cells, write 1 in each. In the third row, write 1 in each end cell, and in the middle cell write the 2 numbers of the cells above it, added together. That is the meaning of the word pūrṇa, "full".

He then reads the rows: the 3-cell row is the 2-syllable meter, with 1 pattern all heavy, 2 with 1 light syllable and 1 all light. The code builds the same triangle:

               1
             1   1
           1   2   1
         1   3   3   1
       1   4   6   4   1
     1   5  10  10   5   1
   1   6  15  20  15   6   1

The last row says that of the 64 patterns of 6 syllables, 1 has no light syllable, 6 have 1, 15 have 2, 20 have 3, 15 have 4, 6 have 5 and 1 has 6.

The Python

This is the method above in Python, following Halayudha's reading.

def prastara(n: int) -> list[str]:
    """All n-syllable patterns of g (heavy) and l (light), in Pingala's order."""
    rows = ["g", "l"]
    for _ in range(n - 1):
        rows = [row + "g" for row in rows] + [row + "l" for row in rows]
    return rows


def nashta(row: int, n: int) -> str:
    """The pattern in a given row: halve if even and write l, else add 1, halve, write g."""
    pattern = ""
    for _ in range(n):
        if row % 2 == 0:
            pattern, row = pattern + "l", row // 2
        else:
            pattern, row = pattern + "g", (row + 1) // 2
    return pattern


def uddishta(pattern: str) -> int:
    """The row of a pattern: from the right, double at each syllable, take 1 off at each g."""
    row = 1
    for syllable in reversed(pattern):
        row = 2 * row - (1 if syllable == "g" else 0)
    return row


def sankhya(n: int) -> int:
    """2**n by Pingala's marks: 2 for a halving, 0 for taking 1 off, then square or double."""
    marks = []
    while n:
        marks.append(2 if n % 2 == 0 else 0)
        n = n // 2 if n % 2 == 0 else n - 1
    count = 1
    for mark in reversed(marks):
        count = count * count if mark == 2 else count * 2
    return count


def meru(n: int) -> list[list[int]]:
    """Halayudha's meru: 1 at the ends of each row, the sum of the 2 cells above inside."""
    rows = [[1]]
    for _ in range(n):
        above = rows[-1]
        rows.append([1] + [a + b for a, b in zip(above, above[1:])] + [1])
    return rows


print(prastara(3))  # ['ggg', 'lgg', 'glg', 'llg', 'ggl', 'lgl', 'gll', 'lll']
print(nashta(6, 6), uddishta("lglggg"))  # lglggg 6
print(sankhya(6))  # 64
print(meru(6)[6])  # [1, 6, 15, 20, 15, 6, 1]

The repo version checks its inputs, starts uddishta at the last l as Halayudha reads the sutra, returns Halayudha's column of marks from sankhya_marks, and adds the counts by beats described below. The tests run Halayudha's examples (the 2-syllable list, the 6th 6-syllable pattern, the marks and count for 6 syllables, the counts up to 4,096, the first meru rows) and check the 3-syllable list against the order of the 8 gaṇas. Property tests with Hypothesis check uddishta and nashta against the binary reading for patterns up to 60 syllables, sankhya against 2**n up to n = 2,000, and the meru against math.comb for 40 rows.

Against the modern methods

Each of Pingala's rules has a modern counterpart in Python's standard library:

PingalaModern
prastaraitertools.product("gl", repeat=n), each tuple reversed
uddishtaint(bits[::-1], 2) + 1
nashtaformat(row - 1, "b")
sankhya2 ** n
meru prastaramath.comb(n, k)

The tests check each pair against each other. Python stores the bits of a number. Pingala's rules go from a number to a pattern and back by halving and doubling, and never write the number in base 2.

Counting by beats: the numbers now called Fibonacci

Some Sanskrit and Prakrit meters fix the number of beats (mātrā) per line: a light syllable is 1 beat and a heavy one 2. A rhythm of m beats ends either in a heavy syllable after a rhythm of m - 2 beats, or in a light one after a rhythm of m - 1 beats. So each count is the sum of the 2 before it: 1, 2, 3, 5, 8, 13, 21.

Pingala's sutras do not state this rule. Parmanand Singh's survey (Historia Mathematica 12, 1985) treats Pingala as the first authority whose writings indicate the numbers, because the commentator Yādavaprakāśa reads sutra 21, miśrau ca, as also meant for beat-counted meters. That rests on the commentator's reading. His century is uncertain. Singh calls him Yādava and puts him in the 10th century. If he is the Yādavaprakāśa who taught Rāmānuja, as the Library of Congress heading assumes, he belongs to the 11th. Singh then traces the explicit rule:

  • Virahāṅka, Vṛttajātisamuccaya, between 600 and 800 CE, gives the rule: the variations of the 2 previous meters, mixed, give the number for the next.
  • Gopāla, whose commentary on Virahāṅka survives in a palm-leaf manuscript copied between 1133 and 1135, works the numbers 3, 5, 8, 13 and 21.
  • Hemacandra, Chandonuśāsana, c. 1150, states the rule and lists 1, 2, 3, 5, 8, 13, 21, 34.

All 3 are earlier than Leonardo of Pisa's Liber Abaci of 1202. The repo's matra_prastara lists the rhythms in the order Singh describes, and the test checks the 13 rhythms of 6 beats against his Table II.

Parallels and lineage

  • Bharata, Nāṭyaśāstra (2nd century BCE to 1st century CE, per Shah). Gets the counts of patterns by number of light syllables by repeated partial sums of 1, 2, ..., n, which gives the same numbers as the triangle.
  • Virahāṅka, Vṛttajātisamuccaya (7th century CE). Shah reports that he is the only author before Halayudha to describe the meru construction. He gives 2 methods: first the partial sums, which he calls sūci, "needle", then the meru.
  • Blaise Pascal, Traité du triangle arithmétique (written 1654, printed 1665). The same triangle, used for the same counts of combinations. No source I have read connects Pascal to the Indian texts.
  • Gottfried Wilhelm Leibniz, "Explication de l'arithmétique binaire" (1703). Binary as a number system, with arithmetic in it. Pingala's rules do not do arithmetic in base 2, and no source I have read connects Leibniz to them.

What is debated

  • Whether sutra 34 describes the triangle. Halayudha says it does. Albrecht Weber, in Über die Metrik der Inder (1863), said the words do not show it. Ludwig Alsdorf (1933) defended Halayudha. Jayant Shah agrees with Weber about this sutra, but argues that a sutra Weber quotes from the Yajus recension of the text, ekottarakramaśaḥ pūrvapṛktā lasaṃkhyā, describes the counts by repeated partial sums, so the triangle's numbers can still be traced to Pingala.
  • Whether to call this binary. B. van Nooten's 1993 paper "Binary numbers in Indian antiquity" made the binary reading widely known. The correspondence with base 2 is exact. Pingala's numbers are ordinary numbers and his patterns are words; he did not write numbers in base 2.
  • Zero. Popular accounts credit Pingala with zero. Śūnya in sutras 29 and 30 marks a step in the count. Whether a written symbol was used for it in Pingala's time, the text does not say.
  • The wording. Editions differ: the 1874 edition reads sutra 27 as tato 'py ekaṃ jahyāt, "then also take away 1", where the edition Kulkarni uses reads tato gy ekaṃ jahyāt, "then, at a g, take away 1". The procedure is the same.

Key takeaways

  • Pingala's Chandaḥśāstra (date debated; 2nd century BCE in Shah, perhaps 3rd in Plofker) ends with 15 sutras that list, index and count every pattern of heavy and light syllables.
  • With g as 0 and l as 1, read from the right, a pattern's row number is its binary value plus 1. The rules to go from row to pattern and back are halving and doubling.
  • The counting rule computes 2^n by repeated squaring, recording each step as a mark of 2 or 0.
  • Halayudha's 10th-century commentary turns the last sutra into the meru prastara, the triangle now called Pascal's triangle. Whether Pingala meant it is disputed.
  • The code, tests and Halayudha's examples are in ancient-algorithms. The next post in the series is on Panini's Ashtadhyayi as a rewrite system.

Sources

Footnotes

  1. Kulkarni's paper, which uses A. Sharma's 2001 edition, numbers the combinatorial sutras 8.20 to 8.35 and reads the last 2 as pare pūrṇam and pare pūrṇam iti. The 1874 edition reads sutra 33 as pareṇa pūrṇam. I normalized the spelling arddha in the 1874 print to ardha. ↩

Common questions

Did Pingala invent the binary system?↓

Pingala gave rules that list all patterns of heavy (g) and light (l) syllables and turn a pattern into its row number and back. If you write g as 0 and l as 1, with the leftmost syllable as the lowest digit, the row number is that binary number plus 1. He did not write numbers in base 2 or do arithmetic in it. Binary arithmetic as a number system was set out by Leibniz in 1703, and no source I have read links the 2.

What is the meru prastara?↓

The meru prastara is a triangle of cells in which the end cells of each row hold 1 and every inner cell holds the sum of the 2 cells above it. Row n gives how many n-syllable patterns have 0, 1, 2 and so on light syllables, so it is the triangle now called Pascal's triangle. Halayudha's 10th-century commentary on Pingala's Chandahshastra describes it as the meaning of Pingala's last sutra. Jayant Shah traces the construction first to Virahanka (7th century), who gives a partial-sums method (suci) and then the meru; Bharata's Natyasastra already gets the same numbers by partial sums.

Was the Fibonacci series invented in India?↓

The numbers 1, 2, 3, 5, 8, 13 count the rhythms that fill a fixed number of beats, with a light syllable worth 1 beat and a heavy one worth 2. Virahanka (between 600 and 800 CE) gives the rule that each count is the sum of the 2 before it, Gopala (before 1135) works the numbers, and Hemacandra (c. 1150) lists 1, 2, 3, 5, 8, 13, 21, 34. All 3 are earlier than Fibonacci's Liber Abaci of 1202. Parmanand Singh documents this in Historia Mathematica (1985), and treats Pingala as the first to show knowledge of the numbers, through a 10th-century commentator's reading of 1 of his sutras.

Is Pascal's triangle in Pingala's sutras?↓

That is disputed. Halayudha, writing about 1,000 years after Pingala, reads the last sutra, pare purnam iti, as an instruction to build the triangle. Albrecht Weber (1863) said the words do not support that reading. Jayant Shah agrees with Weber on that sutra but argues that a different sutra in another recension of the text describes the same counts.

When did Pingala live?↓

No one knows for certain. Jayant Shah gives the 2nd century BCE, and Kim Plofker perhaps the 3rd, as David Mumford's review reports. A later tradition makes Pingala the younger brother of the grammarian Panini, which would put him earlier.

Share this
← More writing Get in touch