India and Computer Science: by J. M. Manasa and Monica Rekhan
Posted on August 20, 2012
“If I were asked under what sky the human mind has most fully developed some of its choicest gifts, has most deeply pondered on the greatest problems of life, and has found solutions, I should point to India.”- Max Mueller
India has been the cradle of many major inventions and discoveries which have steered progress in science and technology. From the discovery of zero to plastic surgery, Indian scholars have made a major impact on development.
So, in this independence week edition of our blog, let us take pride in the revolutionary milestones which have been pointers to innumerable memory locations of development in the field of computer science.
Being computer science students, binary is our second mother tongue. Binary numbers were discovered in the west by German mathematician Gottfried Leibniz in 1695. However, evidence proves that binary numbers were used in India prior to 2nd century A.D., more than 1500 years before their discovery in the west.
The source of this discovery is a text on music by Pingala named “Chhandahshastra” meaning science of meters. This text falls under the category of “Sutra” or aphorismic statements. Detailed discussions of these short but profound statements are found in later commentaries. “Chhandahshastra” can be conservatively dated to 2nd century A.D. Little is known about Piṅgala himself. In Indian literary tradition, he is variously identified either as the younger brother of Pāṇini (4th century BCE), or as Patañjali, the author of the Mahabhashya (2nd century BCE). Pingala developed mathematical concepts for describing prosody (study of metres in poetry), and in doing so presented the first known description of a binary numeral system. He used binary numbers in the form of short and long syllables (the latter equal in length to two short syllables), making it similar to Morse code.
Pingala describes the formation of a matrix in order to give a unique value to each meter. An example of such a matrix is as follows:
0 0 0 0 numerical value 1
1 0 0 0 numerical value 2
0 1 0 0 numerical value 3
1 1 0 0 numerical value 4
Use of zero is sometimes mistakenly ascribed to Pingala due to his discussion of binary numbers, usually represented using 0 and 1 in modern discussion, while Pingala used short and long syllables. As Pingala’s system ranks binary patterns starting at one (four short syllables—binary “0000”—is the first pattern), the nth pattern corresponds to the binary representation of n-1, written backwards.
From the discovery of the binary number system, let us move centuries into the future to the world of computer hardware. In the field of which, we have our very own Vinod Dham, popularly known as “Father of the Pentium Chip”, for his contribution to the development of PENTIUM PROCESSORS from Intel.
Pentium is a brand of x86-compatible microprocessors produced by Intel. As a direct extension of the 80486 architecture, P5 included dual integer pipelines, a faster FPU, wider data bus, separate code and data caches and features for further reduced address calculation latency.
When talking about India’s contribution to computer science, an indispensable name would be Dr. Raj Reddy, the first person of Asian origin to receive ACM Turing Award, whose major research interest has been in exploring the role of “Technology in Service of Society” and “Universal Digital Library Project”. The project includes efforts to archive 1000 newspapers for the next 1000 years and provide online access to UNESCO heritage sites.
Raj Reddy with his team has done historic demonstrations of spoken language systems, e.g. voice control of a robot, large vocabulary connected speech recognition, speaker independent speech recognition, and unrestricted vocabulary dictation. Task Oriented Computer Architectures, Analysis of Natural Scenes, Universal Access to Information, and Autonomous Robotic Systems has expanded in new dimensions because of their contributions. Most notably the “blackboard model” for coordinating multiple knowledge sources has been adopted across the spectrum of applied artificial intelligence.
Thus rightly, it is a classic example of India’s contribution to Computer Science and Artificial Intelligence.
After the binary number system, Pentium chip and the artificial Intelligence’s pioneer, let us now move into the world of algorithms and see what India has to offer here. A group of three computer scientists from IIT Kanpur got India the 2006 Gödel Prize and the 2006 Fulkerson Prize for an algorithm which is called the AKS Primality test.
The AKS primality test , also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test, is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled “PRIMES is in P”.
The algorithm determines whether a number is prime or composite in polynomial time.
The uniqueness of the algorithms lies in the fact that AKS is the first primality-proving algorithm to be simultaneously general, polynomial, deterministic, and unconditional. Previous algorithms had been developed for centuries but achieved three of these properties at most, but not all four.
- The AKS algorithm can be used to verify the primality of any general number given. Many fast primality tests are known that work only for numbers with certain properties. For example, the Lucas–Lehmer test for Mersenne numbers works only for Mersenne numbers, while Pépin’s test can be applied to Fermat numbers only.
- The maximum running time of the algorithm can be expressed as a polynomial over the number of digits in the target number.
- The algorithm is guaranteed to distinguish deterministically whether the target number is prime or composite. Randomized tests, such as Miller–Rabin and Baillie–PSW, can test any given number for primality in polynomial time, but are known to produce only a probabilistic result.
- The correctness of AKS is not conditional on any subsidiary unproven hypothesis. In contrast, the Miller test is fully deterministic and runs in polynomial time over all inputs, but its correctness depends on the truth of the yet-unproven generalized Riemann hypothesis.
The AKS primality test is based upon the following theorem: An integer n (≥ 2) is prime if and only if the polynomial congruence relation
(x-a)^n = (x^n-a) (mod n) ….(1)
holds for all integers a coprime to n (or even just for some such integer a, in particular for a = 1). Note that x is a free variable. It is never substituted by a number; instead we have to expand (x-a)^n and compare the coefficients of the x powers.
nCk = 0 (mod n)
for all 0<k<n if and only if n is prime.
(x-a)^n = (x^n-a) (mod(n,x^r-1) …(2)
which is the same as:
(x-a)^n – (x^n-a) = nf + (x^r-1)g …(3)
for some polynomials f and g. This congruence can be checked in polynomial time with respect to the number of digits in n, because it is provable that r needs be logarithmic with respect to n. All primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). However, some composite numbers also satisfy the relation. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that, if the congruence holds for all such a in A, then n must be prime.
In the first version of the above-cited paper, the authors proved the asymptotic time complexity of the algorithm to be Õ(log^12(n)). In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor. However, the upper bound proved in the paper was rather loose; indeed, a widely held conjecture about the distribution of the Sophie Germain primes would, if true, immediately cut the worst case down to Õ(log^6(n)).
Commenting on the impact of this discovery, Paul Leyland (a British number theorist noted) : “One reason for the excitement within the mathematical community is not only does this algorithm settle a long-standing problem, it also does so in a brilliantly simple manner. Everyone is now wondering what else has been similarly overlooked”
Thus, beginning from the binary number system to Pentium chips and ingenious algorithms, India has made a static mark in the dynamic world of computers. Our country has shown great potential for high-calibre research in computer science which can be reflected in the fact that the growth rate of our software industry has been tremendous in the recent past. So, India has and will function as an integral part of the developments in computer science that returns invaluable breakthroughs.