Euclidean Algorithm - Historical Development

Historical Development

The Euclidean algorithm is one of the oldest algorithms still in common use. It appears in Euclid's Elements (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for real numbers. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume, and the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.

The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (about 375 BC). The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle.

Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arise in astronomy and making accurate calendars. In the late fifth century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described by Chinese mathematician and astronomer Sun Tzu, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). In Europe, it was likewise used to solve Diophantine equations and in developing continued fractions. The extended Euclidean algorithm was published by the English mathematician Nicholas Saunderson, who attributed it to Roger Cotes as a method for computing continued fractions efficiently.

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832. Gauss mentioned the algorithm in his Disquisitiones Arithmeticae (published 1801), but only as a method for continued fractions. Peter Dirichlet seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory. Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two-square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, however, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals.

" is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval.

The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed in recent years, such as the Ferguson–Forcade algorithm (1979) of Helaman Ferguson and R.W. Forcade, and its relatives, the LLL algorithm, the HJLS algorithm, and the PSLQ algorithm.

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy. The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to xmy stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.

Read more about this topic:  Euclidean Algorithm

Other articles related to "historical development, development, developments, historical":

Seventh-day Adventist Theology - Theological Variation - Historical Development
... Seventh-day Adventist theology has undergone development from the beginnings of the movement ... Doctrinal development has been associated with significant events, including the 1888 Minneapolis General Conference and discussions with evangelicals in the middle of the 20th ... As a consequence of these developments, different theological streams have emerged which today exist alongside the mainstream of the Church ...
Sustainable Gardening - Historical Development
... Many of the eco-friendly principles and ideas espoused by sustainable gardens, landscapes and sites perpetuate sustainable practices established as a reaction to resource-intensive industrial agriculture ... These practices were established as movements for self-sufficiency and small-scale farming based on a holistic systems approach and ecological principles ...
Native Americans In The United States - History - Pre-Columbian
... of the Athabascan- speaking peoples, including the present-day and historical Navajo and Apache ... based on the people's adoption of maize agriculture, development of greater population densities, and chiefdom-level complex social organization from 1200 CE to 1650 CE ... This in turn led to the development of specialized skills among some of the peoples ...
Essen, Germany - Politics - Historical Development
... During the German Revolution of 1918–19, Essen was the home of the Essen Tendency (Essener Richtung) within the Communist Workers' Party of Germany ... In 1922 they founded the Communist Workers' International ...

Famous quotes containing the words development and/or historical:

    The Cairo conference ... is about a complicated web of education and employment, consumption and poverty, development and health care. It is also about whether governments will follow where women have so clearly led them, toward safe, simple and reliable choices in family planning. While Cairo crackles with conflict, in the homes of the world the orthodoxies have been duly heard, and roundly ignored.
    Anna Quindlen (b. 1952)

    Culture is the name for what people are interested in, their thoughts, their models, the books they read and the speeches they hear, their table-talk, gossip, controversies, historical sense and scientific training, the values they appreciate, the quality of life they admire. All communities have a culture. It is the climate of their civilization.
    Walter Lippmann (1889–1974)