A History of Algorithms

As for squares and roots equal to a number, it is as when you say this: a square and ten of its roots equal thirty-nine dirhams.

The basic arithmetic operations of the elementary school, multiplying and dividing, appear to have derived from extremely early economic needs, certainly earlier than the emergence of civilisations using writing. One of the earliest pieces of evidence of an algorithm of this type is to be found on a clay tablet found at Shuruppak, near Baghdad which concerns a problem of sharing. Engraved by a Sumerian at about 2500 BC, this tablet (see Section 1.1) illustrates the first of the ten episodes which we have chosen to illustrate a history which would occupy several volumes if it were to be written up in detail.

The expression magic square is commonly used for any arrangement of squares, like the squares on a board for playing chess or draughts, in which the individual square cells contain numbers such that the sum of the numbers along any row, column or diagonal produces the same result. A magic square containing n rows and n columns is called an order n magic square. Mathematically, it is often useful to consider the square as a particular square matrix possessing the magic constant S _n which is equal to the common sum of its rows, columns and diagonals.

“A lance has a half and a third in the water and 9 palms outside. I ask you how long is it?” This question proposed by Francès Pellos, a fifteenth century nobleman from Nice, would not be thought to present any particular difficulty nowadays for anyone who knows a little algebra. If we let x stand for the length of the lance, we have to solve the equation:

We have already remarked in the introduction to this book, that Euclid’s algorithm often represents for the mathematician the prototype of algorithmic procedure, and that it has relevance right up to today. It can be of use, not only in the search for the greatest common divisor, as described by Euclid himself (Section 4.1), but also, by adapting the procedure, in the solution of indeterminate equations, leading to Bézout’s identity (Section 4.3). It allowed al-Khayyam to compare two ratios, or to show that they were equal (Section 4.2); this appears even more clearly in the writing of continued fractions which were systematically studied by Euler (Section 4.4). Finally, what may appear surprising, the algorithm can be used in Sturm’s method for determining the number of real roots of an algebraic equation (Section 4.5).

Well before Archimedes showed how to work out the circumference of a circle, empirical values had been used for the ratio of the circumference of a circle to its diameter, which we call π. The quotation from the Bible suggests that it might be taken to be 3, and the Rhind Papyrus indicates that the Egyptians considered it could be estimated as equal to 4.(1 - 1/9)²=3.16... We should, however, be careful to avoid any error at this stage: there is no way that π can ever be considered as a number in a formula. Right from the start, it was never written, nor ever thought of, in terms of algebraic expressions. Instead methods of calculations, or ‘algorithms’ were devised, which were set out using the language of the times.

Newton’s method is remarkable both for the simplicity of its principle — based on linear approximation, and for its efficiency — often a very rapid convergence. It is known, in practice, by two names, depending on the circumstances in which it is used. When finding successive approximations to the numerical solution of an equation: P(y)=0, it is called the tangent method or simply Newton’s method. When flnding y expressed as a series in x, given an equation: F(x,y)=0, it is called Newton’s polygon method. These two versions, for flnding numerical and algebraic solutions, are both described by Newton in his Method of Fluxions and Infinite Series.

Does a procedure exist for finding all the prime numbers? This question is, without doubt, as old as the science of Arithmetic itself and, as we shall see, leads on to other algorithmic problems. In this chapter we shall look at several famous algorithms in the history of Arithmetic.

The solution of some ancient problems can be considered today as the solution of systems of linear equations. We come across such problems frequently in Babylonian and Egyptian mathematics, and also in Indian mathematics of the Middle Ages, as well in Islamic countries and in Europe [29]. It becomes quite difficult however to decide in which branch of mathematics we should place the corresponding algorithms for solving these problems. Their solution is given as a sequence of instructions, followed by a validation of the results, presented in ways that make their use quite general. However, in order to assess the validity of these algorithms, and to help our understanding, we shall consider them as belonging to the domain of algebra, as we understand the term today. Of course, describing these old problems as being problems about solving systems of linear equations involves an anachronism, since the idea of systems of equations is very much later. We have already seen such examples in Chapter 3, particularly with the text by Clavius, where we saw that he used the method of repeated double false position to solve, what we would now call a ‘system of order 3’ (see also [23]).

The construction of tables turned out to be of vital importance for facilitating calculations and for avoiding the need to carry out the same operations many times. We have seen how tables have been constructed from the earliest times, for example, the Babylonians produced tables for calculating ‘inverses’ (Section 1.2 above). In Astronomy, trigonometric tables have played a major role, and these correspond to the tables of chords that Ptolemy produced in the 2nd century (Section 10.1). A table of logarithms is another type of table, specifically introduced to make calculations easier, by transforming multiplications into additions; we shall look at the decimal tables established by Briggs in the 17th century following on from the work of Napier (Section 10.2).

The origin of the meaning of quadrature, or squaring, was to find a square having the same area as that of some given geometrical figure. The quadrature of a circle, or ‘squaring the circle’, is the best known example. The meaning of quadrature quickly began to take on an extended meaning of comparing the areas of two plane figures, one of which was already known — for example, a figure bounded by straight lines. Thus quadrature came to mean establishing a ratio between two plane figures, rather than measuring an area in the proper sense of the word.

Right from the birth of the infinitesimal calculus in the 17th century, certain problems arose, in geometry and mechanics, that gave rise to first order differential equations. There followed a systematic study of differential equations in the 18th century, and particularly in the 19th century, as a consequence of applying Newton’s Laws of mechanics to determine the trajectories of celestial bodies, since the study of a mechanical system of n ‘material points’ is equivalent to the study of 3n second order differential equations.

The idea of approximating a function has already been raised when we considered interpolation. We noted there the difficulty in certain cases of making a clear distinction between two points of view. In principle, with interpolation, we construct a function which has to take specific values for a finite number of values of the variable, whereas, with approximating, we look for a function which approximates ‘as well as possible’ the values of the other function, and this for all values of the variable over a certain interval. We can say that approximation is global in nature, since the approximating function has a relation to all the values of the variable over an interval, which is not the case with an interpolation function, only required to be equivalent to the interpolated function for a finite number of values (which must necessarily be the case when the values of the function are obtained experimentally).

So far we have looked at algorithms designed to solve particular problems. For the most part, algorithms were in use long before it was felt necessary to give a clear definition of what is meant by an algorithm. Today, an algorithm is defined as a finite and organised set of instructions, intended to provide the solution to a problem, and which must satisfy certain conditions. An example would be [10]: