Close

Pingala’s Algorithm Part II: Binary Conversion

Pingala’s Algorithm for Binary Conversion

Today’s digital technologies work on the binary number system. All your data is encoded in binary numbers, 0 and 1. For example, the number 235 is 1110 1011 in binary (base-two number system). But how do you convert a decimal number into its binary equivalent? Let us look at it in this article.

We generally use the decimal place-value number system. In this system, we have

235 = (2 * 100) + (3 * 10) + (5 * 1) = (2 * 10^2) + (3 * 10^1) + (5 * 10^0)

Now, we can use any number, instead of just 10, as our base for the place-value number system.

We can use a polynomial in base number to represent a number in a place-value number system. Let x, be any base number. Then, we have

anxn + an-1xn-1 + an-2xn-2 + … + a2x2 + a1x1 + a0x0 = (anan-1an-2…a2a1a0)x

Here, an, an-1, an-2, …, a2, a1, a0 are the digits in the base x number system. They can take on values from 0 to (x – 1).

Now, let us represent the decimal number 235 in some base x number system.
We have … + anxn + an-1xn-1 + an-2xn-2 + … + a2x2 + a1x1 + a0x0 = (235)10 – eqn (1)

Here,we don’t know how many digits in base x number system are required to (235)10.

Now, how do we find the digits in the base x number system?
What if we divide both sides of Eqn (1) with x?

We get, a0 as the remainder on the left side of Eqn (1). Similarly, we also get a reminder on the right side of Eqn (1). This remainder will be the digit in the lowest value place.

We also get … + anxn-1 + an-1xn-2 + an-2xn-3 + … + a2x1 + a1 as the quotient. This will be our new dividend for getting the digit in the second-lowest value place. Let us divide it by x.

We get, a1 as the remainder. This remainder will be the digit in the second-lowest value place.

We also get … + anxn-2 + an-1xn-3 + an-2xn-4 + … + a3x + a2 as the quotient. This will be our new dividend for getting the digit in the third lowest value place. Let us divide it by x.

We get, a2 as the remainder. This remainder will be the digit in the third lowest value place.

We also get .. + anxn-3 + an-1xn-4 + an-2xn-5 + … + a3 as the quotient. This will be our new dividend for getting the digit in the next higher value place.

To get the digits in the higher value places go on repeating the above procedure. The process stops when the quotient becomes zero.

Thus, we get the representation of (235)10 in base x number system as (… anan-1an-2 … a2a1a0)x.

As an example, let us convert the decimal number 235 into binary.
Since we want to convert a decimal number 235 into binary we will divide it by 2.
Step 1) 235/2
Quotient = 117, remainder = 1
Thus, 1 will be the digit in the lowest value place.
Step 2) 117/2
Quotient = 58, remainder = 1
Step 3) 58/2
Quotient = 29, remainder = 0
Step 4) 29/2
Quotient = 14, remainder = 1
Step 5) 14/2
Quotient = 7, remainder = 0
Step 6) 7/2
Quotient = 3, remainder = 1
Step 7) 3/2
Quotient = 1, remainder = 1
Step 8) 1/2
Quotient = 0, remainder = 1
Since here, the quotient is 0, the division process comes to an end.
Thus, the binary representation of the decimal number 235 is 1110 1011.

Pingala was the first person to have done such a binary conversion. Let us look at how he must have developed such an algorithm.

In my previous article, I had described how Pingala had developed technique (pratyay, प्रत्याय) or algorithm called Prastaar (प्रस्तार , meaning to unfold or to open up) for enlisting all the possible combinations of Guru (G) and Laghu (L) syllables for a quarter with length n letters.

Let me present here a prastaar for a quarter with length 5 letters. Refer to Table 1

Table 1

During ancient times, the prastaar used to be written on the sand. There was a possibility that the wind might blow away the sands and erase some rows of the prastaar. So, how do you restore an erased/damaged row?

Pingala had developed a technique (pratyay, प्रत्याय) or an algorithm called Nashtam (नष्टम्) to regenerate the sequence of Guru and Laghu syllables of a row with a given row/index number.

If we replace G with ‘0’ and L with ‘1’ in Table 1, we get a binary number system developed by Pingala. Refer to Table 2.

Table 2

I would now like to draw your attention to two things in Table 2.
1) In the binary sequence generated by Pingala, the numbers are written with the higher place value digits to the right of lower place value digits. As can be seen from Table 2, the binary sequences generated by Pingala are mirror images of the modern representation of binary numbers.
2) The counting of row/index numbers begins from 1. It means that the row number is one more than the value of the binary number.

Pingala’s rule for binary conversion

लर्धे | सैके ग् | (छन्दः शास्त्रम् 8.24-25)

  • To find the pattern in a row of the prastaar, start with the row number.
  • Halve it (if possible) and write an L.
  • If it cannot be halved, add one and halve and write a G.
  • Proceed till all the syllables of the metre are found.

Let us now find the nth row in a prastaar for m characters in a quarter.

We have, n = value of the number + 1

Let bm-1bm-2…b2b1b0 represent the binary number having m bits. We can write this binary number as a polynomial in 2 as

(bm-1 * 2m-1) + (bm-2 * 2m-2) + … + (b2 * 22) + (b1 * 21) + b0

Now, we have

(bm-1 * 2m-1) + (bm-2 * 2m-2) + … + (b2 * 22) + (b1 * 21) + b0 + 1 = n – eqn (2)

In eqn (2), b0 is the bit in the lowest value place. To get the value of b0 we should divide both the sides of eqn (2) by 2. In this two scenarios can occur:

1) The number n is divisible by 2

It means that, b0 + 1 = 2, then b0 = 1.

This means that the first letter in the nth row is a Laghu (L) syllable.
This is what was precisely stated as a rule by Pingala. Pingala’s first sutra for binary conversion states that if the number n can be halved, write a Laghu (L) and halve the number.

2) The number n is not divisible by 2

It means that, b0 + 1 = 1, then b0 = 0.

This means that the first letter in the nth row is a Guru (G) syllable.
Pingala’s second sutra for binary conversion states that if the number n cannot be halved, write a Guru (G), then add a 1 to the number n and halve it.
Let us add 1 to both sides of Eqn (2):

(bm-1 * 2m-1) + (bm-2 * 2m-2) + … + (b2 * 22) + (b1 * 21) + b0 + 1 + 1 = n + 1  – eqn (3)

The quotient of this division will be the dividend to find the next high value place digit, b1.
The same procedure is repeated to find the remaining binary digits of the row. The division stops when we get all the m digits of the row.

Let me illustrate the above procedure by applying it to find the 22nd row of a prastaar for a quarter of length 5 (Table 2).
We have, n = 22.
Step 1) n = 22. It is divisible by 2. Therefore the first letter in the row is Laghu (L).
Now, halve the number:

n = n/2 = 22/2 = 11

Step 2) n = 11. It is not divisible by 2. Therefore the second letter in the row is a Guru (G).
Now, add a 1 to the number and then halve it.
n = n + 1 = 11 + 1 = 12
n = n/2 = 12/2 = 6

Step 3) n = 6. It is divisible by 2. Therefore the third letter in the row is a Laghu (L).
Now, halve the number:
n = n/2 = 6/2 = 3

Step 4) n = 3. It is not divisible by 2. Therefore the fourth letter in the row is a Guru (G).
Now, add a 1 to the number and then halve it.
n = n + 1 = 3 + 1 = 4
n = n/2 = 4/2 = 2

Step 5) n = 2. It is divisible by 2. Therefore the fifth letter in the row is a Laghu (L).
Now, halve the number:

n = n/2 = 2/2 = 1

Thus, the arrangement of Guru and Laghu syllables in the 22nd row of a prastaar for a quarter of length 5 is LGLGL. Checking this in Table 2, we find it to be correct.

From the above discussion we can infer that:
1. Pingala and Indian mathematicians of his time had the knowledge of place-value number systems.
2. They had the knowledge of long division of polynomials.
3. Pingala understood and had developed the algorithm for radix conversion.

Explore Pingala’s Binary Number System Part I


We welcome your comments at feedback@indictoday.com