A History of Algorithms: From the Pebble to the Microchip

For most people, mathematics is a tool for getting answers. For them, to learn mathematics is to learn the techniques for finding those answers. The techniques are the mathematics, be they rules for multiplication, ways to solve differential equations, or methods to invert matrices. It is a relatively small minority of users of mathematics, mostly those of us who call ourselves "mathematicians", who think of mathematics as theory rather than as technique.

It has not always been thus. Mathematicians of earlier ages mix technique with theory. The theoretician Euclid also gave us the Euclidean Algorithm. Newton's method may not have been discovered by Newton, but the man who gave us the abstractions of fluxions and fluents also solved equations and interpolated polynomials. The same C. F. Gauss whose name is on so many theorems in number theory and complex analysis also gave us Gaussian elimination and a variety of other iterative methods for solving equations. The list goes on. The greatest mathematicians from a dozen centuries advanced the techniques of mathematics as well as its theories.

It is fitting, therefore, that a history of mathematics present the subject via its techniques. Such is the approach of A History of Algorithms.

Chabert and his six co-authors have selected over a hundred original texts, expertly translated and sprinkled across 15 chapters and more than a hundred sections. Topics range from Sumerian division algorithms to Turing machines, with scores of topics in between.

The discussion Newton's methods (Chapter 6) for finding roots of equations is fascinating. This section features an extract from Newton's De Methodus Fluxionum et Serierum infinitorum, written sometime between 1664 and 1671. If you read this expecting to find the familiar recurrence relation involving f(x)/f'(x), you will be surprised or disappointed. There is no recurrence relation. There is no ratio. There isn't even a derivative. Instead, there is a worked-out example finding the roots of a cubic and involving auxiliary polynomials and meticulous substitutions. It resembles Lagrange's continued fraction methods (Chapter 7) more than it resembles the iterative method we now call the Newton-Raphson method.

Raphson's 1697 version is much more like a modern presentation. Our authors go on to show the improvements to the method and its presentation by Simpson, Mourraille and Cauchy. We see how studies of the method helped lead Cauchy to his understanding of convergence.

Approximate solutions of differential equations (Chapter 12) form the subject of a particularly rich chapter. Like so many other topics in mathematics, it begins with Euler — two pages on Euler's method from his Institutionum Calculi Integralis from 1768. We leap over a hundred years to Picard's 1890 Mémoire sur la théorie des équations aux dérivées partielles et la méthode des approximations successives. Five years later, Runge presents his ideas, describing them as using Simpson's rule where Euler used something like the trapezoid rule. Six years after that, in 1901, Kutta added his improvements, giving the Runge-Kutta method the second half of its name.

More than half the book is devoted to topics that are typically found in a course in numerical analysis, quadrature and integration, interpolation, approximate solutions to differential equations, approximation of functions and acceleration of convergence. Still, there is good coverage of other topics as well.

Chapter 3 is devoted to methods of false position as they were used in Mesopotamia, Egypt, China, India, Arabia and Medieval and Renaissance Europe. The Euclidean algorithm and the continued fractions that are its descendents occupy Chapter 4. Chapter 8 is filled with algorithms in number theory and arithmetic including the sieve of Eratosthenes, quadratic residues, tests for primality and factorization algorithms.

The chapter on solving systems of linear equations (Chapter 9) is somewhat difficult because so much of the important work in the subject was done before matrix notation was invented. Cramer's rule came surprisingly early, in 1750. He used a system of superscripts to denote his coefficients, and calculates the numbers we now call determinants by summing over all the permutations of the coefficients. His method of finding the sign of a permutation is quite interesting.

Gauss, hardly easy to read even in the best of circumstances, is almost impenetrable when, in 1810, he uses a system of primes and double primes to denote coefficients and square brackets to denote whole sides of an equation as he describes what we now call Gaussian elimination. Our authors rescue us, though, with an illuminating explanation, in modern notation, of what Gauss said.

After fourteen chapters of algorithms from around the world and across so many centuries, the last chapter is devoted to the theory of algorithms themselves. In an unsurprising contrast to the original sources in other chapters, the works of Gödel, Church, Kleene, Turing and Post use notations and terms that are almost identical to the presentations in modern textbooks.

A History of Algorithms is quite a remarkable book. It is a gold mine of well selected and well translated original sources. Most readers will find parts of the book quite challenging, since it covers so many different topics in some depth and because original sources tend to use old and unfamiliar notations and terminology and even archaic sentence structure, and they are seldom as polished as later presentations.

This book could be used as a companion to a numerical analysis course, or as the backbone of a history of mathematics course. In either setting, students would find it challenging, but richly rewarding.

A student who knew all of the material in this book would have a fairly complete undergraduate mathematics education, though a little biased towards numerical analysis. There are few other books that better approximate a complete mathematical education in a single volume.

Ed Sandifer (sandifer@wcsu.ctstateu.edu) is professor of mathematics at Western Connecticut State University and an enthusiastic fan of Leonhard Euler.