Computing the solution to a difficult mathematical problem sometimes involves guessing an answer, and then iteratively refining the answer, hopefully reducing the error to a negligible level.
If the error reduces by a fixed number of digits in each iteration, it is said to have a “Linear Convergence Rate”. If the error reduces such that the number of significant digits doubles in each iteration, it is said to have a “Quadratic Convergence Rate”. Most algorithms known today fall between these two convergence rates.
It is exciting that an algorithm from ancient India has provably “Quartic Convergence Rate”, i.e., double the rate of a quadratically convergent algorithm.
In a very early period of time, Baudhayana had formulas to compute the square-root of a positive number. So did the Babylonians, notably seen in cuneiform tablets. Our story however goes to an entirely different time period — to the beginning of the Common Era.
Heron of Alexandria (10 CE — 70 CE), learnt the Babylonian methods, and had an iterative formula to compute the square root, which can be shown as a quadratically convergent algorithm.
The Bakshali manuscript recently carbon dated to 224 CE, with content copied from much earlier manuscripts, contains a formula to compute the square root, which can be demonstrated to have quartic convergence rate.
I wrote simple Matlab programs to demonstrate the two algorithms.
In Fig.1, we run the Heron formula to find the square root of 256, starting with a guess of 1. We see that it converges to the answer of 16 in 9 iterations.
Fig.2. shows the Bakshali formula to find the square root of the same number 256, starting with a guess of 1. We notice that it converges in about half the iterations of the Heron formula, indicating quartic convergence.
Ancient Indians are known to have used decimal notation and place-value computations. It is highly unlikely that Heron (who might have used clunky Latin or Greek Attic numerals) would have used decimal fractional number computation, or was even capable of iterating a numerical solution (owing to the tedium of Latin/Greek numeral calculation).
We can investigate the behavior of both the algorithms using rounded numbers (by ignoring the fractional parts), and check the square roots of perfect squares.
Fig. 3 shows surprisingly that the rounded-numbers (integer) Heron formula converges quicker than its real-numbers counterpart, taking 7 iterations instead of 9.
Fig.4 shows that the rounded-numbers Bakshali manuscript formula converges in 4 iterations, a bit faster than the real-numbers formula. If the initial guess is closer to the solution, it reliably converges in 2 to 3 iterations for many perfect squares.
Both algorithms can find the square-root of any positive real number, not only those of perfect-squares.
Closing Remarks
Quartic convergent algorithms are highly desirable for iterative algorithms owing to their rapid rate of convergence (and hopefully quicker runtime).
Most iterative algorithms used today have convergence rates between linear to quadratic. As an example, today’s machine learning algorithms with billions of parameters (such as GPT-3), have weak convergence rates between linear to sub-linear.
The discovery of a quartic convergence rate in ancient Indian works shows the high premium placed by ancient Indian scientists on minimal computation algorithms. The Bakshali manuscript writer indicates that he copied from earlier mathematical texts, indicating high antiquity for the methods in the text.
From the convergence behavior observed in this note, it is clear that the Bakshali algorithmic methods were far superior to the computational methods used in ancient Babylon or ancient Greece for square roots, and provides yet another avenue to reject moot assertions by some Western historians that ancient India learnt its mathematics from Babylon or Greece.
Code
Several readers reached out for the sample code. The Heron and Bakshali square root computation code snippets are shown in the images below.
Write these as script files and run in Matlab or in Octave. As noted in the comments, remove the “round” to do real-valued computation for square root of any positive number. If you use “round”, answers will be correct only for perfect squares.
