Close

Pingala’s Algorithm Part V: Algorithm to Calculate the Value of an Exponential


या सृष्टिः स्रष्टुराद्या वहति विधिहुतं या हविर्या च होत्री
ये द्वे कालं विधत्तः श्रूतिविषयगुणा या स्थिता व्याप्य विश्वम् ।
यामाहुः सर्वबीजप्रकृतिरिति यया प्राणिनः प्राणवन्तः
प्रत्यक्षाभिः प्रपन्नस्तनुभिरवतु वस्ताभिरष्टाभिरीशः ॥ १॥

Meaning:

May the Lord who is endowed with the eight visible forms protect you. The eight forms viz.

(1) That is the first creation of the creator (water).

(2) That which conveys to God, the oblation offered according to the customary rites (fire).

(3) That is the sacrificer.

(4) and (5) Those two that regulate time (the sun and the moon).

(6) That which has sound for its quality and which pervades the universe (the ether).

(7) That which they call the source of all seeds (the earth).

(8) That by which the creatures possess breath (air).

This is the first verse of Kalidasa’s Abhijnanasakuntalam which is composed in the Sragdhara (स्रग्धरा) meter. Sragdhara has 21 syllables in each of its quarters. The pattern of Gurus and Laghus in Sragdhara is GGGGLGG LLLLLLG GLGGLGG.

Now, you may ask how many combinations of Gs and Ls are possible for a meter having 21 syllables? Or how many rows will be there in a prastaar for 21 syllables?

Refer to my earlier article How Pingala created the Binary Number system (part 1 of this series). The prastaar for 1 syllable has 2 rows. The prastaar for 2 syllables has 4 rows. The one for 3 syllables has 8 rows and the one for 4 syllables has 16 rows. And so on. The numbers of rows in a prastaar get doubled with every unit increment in the number of syllables. That is, the number of rows in a prastaar of n-syllables is given by Sn = 2^n.

So the number of rows in a prastaar for a quarter having 21 syllables is 2^21. But what is the value of 2^21?

To calculate 2^21, I have to multiply 2 with itself 20 times. That is double the number 20 times. This will be a 20 step process. Is there a more efficient process? Yes!

Let us say I want to calculate a^21.

I can write

a^21 = (a^20) x a

= [(a^10)^2] x a

= [((a^5)^2)^2] x a

= [((a^4 x a)^2)^2] x a

= [(((a^2)^2 x a)^2)^2] x a

Now, this has become a 6 step process instead of a 20 step process.

Let us use this method to calculate S21 = 2^21.

S21 = 2^21 = [(((2^2)^2 x 2)^2)^2] x 2 = [((4^2 x 2)^2)^2] x 2 = [((16 x 2)^2)^2] x 2 = [(32^2)^2] x 2 = [(1024)^2] x 2 = 1048576 x 2 = 2097152

We can have 20,97,152 different meters having 21 syllables. That is there will be 20,97,152 rows in a prastaar for a quarter having 21 syllables.

You must be wondering who must have been the first person to have come up with the algorithm for quick exponential calculations.

Donald Knuth in his book The Art of Computer Programming, Volume 2, Seminumerical Algorithms, has mentioned that it was Pingala who was the first one to have developed such an algorithm in his work Chandahshastra. Pingala had developed an algorithm or pratyay (प्रत्याय) called Sankhya (संख्या) to quickly calculate the value of an exponential.

Pingala’s sutras for the Sankhya pratyay are:

द्विरर्धे | रुपे शून्यम् | द्विः शून्ये | तावदर्धे तद्गुणितम् | (छन्दः शास्त्रम् 8.28-31)

  • If the number is divisible by 2, divide by 2 and write “2”.

  • If the number is not divisible by 2, deduct 1 and write “0”.

  • Proceed till you reach zero.

  • Start with the number 1 and scan the sequence of 2s and 0s from the end.

  • If you encounter “0”, multiply by 2.

  • If “2”, then square.

Let me illustrate this pratyay by calculating 2^21.

  • 21 is not divisible by 2, hence deduct 1 from 21 and write down “0”. We now have, n = 20 and the sequence as 0.

  • 20 is divisible by 2. Hence, n = n / 2 = 20 /2 = 10. Now, the sequence is 0, 2.

  • 10 is divisible by 2. Hence, n = n / 2 = 10 /2 = 5. Now, the sequence is 0, 2, 2.

  • 5 is not divisible by 2. Hence, n = n – 1 = 5 – 1= 4. Now, the sequence is 0, 2, 2, 0.

  • 4 is divisible by 2. Hence, n = n / 2 = 4 /2 = 2. Now, the sequence is 0, 2, 2, 0, 2.

  • 2 is divisible by 2. Hence, n = n / 2 = 2 /2 = 1. Now, the sequence is 0, 2, 2, 0, 2, 2.

  • 1 is not divisible by 2. Hence, n = n – 1 = 1 – 1= 0. Now, the sequence is 0, 2, 2, 0, 2, 2, 0.

  • We have reached “0”, hence we stop the process.

  • We start with the number 1 and scan the sequence from the end.

  • We first encounter a 0, hence we have, 1 x 2 = 2.

  • Then we encounter a 2, hence we have, 2^2 = 4.

  • Again we encounter a 2, hence we have, 4^2 = 16.

  • Then we have 0, hence we have, 16 x 2 = 32.

  • We now have a 2, hence we square the number, 32^2 = 1024.

  • We again have a 2, hence we have, (1024)^2 = 1048576

  • And last we have a 0, hence we have, 1048576 x 2 = 20,97,152.
    S21 = 20,97,152

Let us look at one more example, say S15 = 2^15.

We have n = 15.

  • n = n – 1 = 15 – 1 = 14. Sequence = 0.

  • n = n / 2 = 14/2 = 7. Sequence = 0, 2.

  • n = n – 1 = 7 – 1 = 6. Sequence = 0, 2, 0.

  • n = n / 2 = 6/2 = 3. Sequence = 0, 2, 0, 2.

  • n = n – 1 = 3 – 1 = 2. Sequence = 0, 2, 0, 2, 0.

  • n = n / 2 = 2/2 = 1. Sequence = 0, 2, 0, 2, 0, 2.

  • n = n – 1 = 1 – 1 = 0. Sequence = 0, 2, 0, 2, 0, 2, 0.

So the final sequence is 0, 2, 0, 2, 0, 2, 0.

  • 1 x 2 = 2

  • 2^2 = 4

  • 4 x 2 = 8

  • 8^2 = 64

  • 64 x 2 = 128

  • 128^2 = 16384

  • 16384 x 2 = 32768

Hence we S15 = 32768

Two more sutras are associated with Pingala’s Sankhya pratyay:

द्विर्द्यूनं तदन्तानाम् | (छन्दः शास्त्रम् 8.32)

Meaning: the sum of all sankhyas Sr for r = 1, 2, 3, …, n is

S1 + S2 + S3 + … + Sn = 2Sn – 2

परे पूर्णम् | (छन्दः शास्त्रम् 8.33)

Meaning:

Sn+1 = 2Sn

Pingala’s Sankhya was one of the earliest and quickest methods to calculate the exponential.

Explore Pingala’s Algorithm  Part III,  III, and IV


We welcome your comments at feedback@indictoday.com