ABSTRACT

In the year 300 bc, the city of Alexandria in present-day Egypt was endowed with a magnicent library similar in spirit to the modern institution we call a university. In this Royal Library, which contained reading rooms and a large quantity of books in the form of papyrus scrolls, scholars from diverse parts of the neighboring world, nancially supported by the government in Alexandria, gathered together to carry out research and write about a wide variety of topics, including astronomy, geometry, and music.* One scholar in particular, named Euclid, wrote a book that became one of the best sellers of all time for more than two thousand years. is book titled e Elements contains a wonderful compilation of algorithms (recipes) that were known at that time for solving an extensive variety of geometric problems that many of us have studied in secondary school.† Aside from geometry, Euclid also described a compelling algorithm for solving a fundamental problem concerned with the arithmetic of numbers. is algorithm has found many mathematical and computational applications since then, and is still actively investigated today.‡ Little did Euclid know that 2300 years later this numerical algorithm would be shown to generate traditional musical rhythms used throughout the world. Although some readers may be surprised to learn that numbers and music are intimately related, the German philosopher and mathematician Gottfried Leibniz once wrote: e pleasure we obtain from music comes from counting, but counting unconsciously. Music is nothing but unconscious arithmetic.§

e algorithm in question is one of the oldest and well-known algorithms, described in Propositions 1 and 2 of Book VII of e Elements. Today, it is referred to as the Euclidean algorithm. is algorithm solves the problem of computing the greatest common divisor

of two given natural numbers. e computer scientist Donald Knuth calls it the “granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.” e idea is captivatingly simple. Repeatedly replace the larger of the two numbers by their dierence until both are equal. is last number is then the greatest common divisor. Consider as an example the pair of numbers (3, 8). First, eight minus three equals ve, so we obtain the new pair (3, 5); then, ve minus three equals two giving (3, 2); next, three minus two equals one, which yields (1, 2); and lastly, two minus one equals one, which results in (1, 1). erefore, the greatest common divisor of three and eight is one. is procedure admits a compelling visualization illustrated in Figure 19.1 for the pair of numbers (3, 8). First, construct a 3 × 8 rectangle of unit squares as shown in the upper le . Repeatedly subtract a 3 × 3 square from this rectangle until it is impossible to do so. is leaves a 2 × 3 rectangle remaining (upper right). Now proceed to remove 2 × 2 squares from this 2 × 3 rectangle until it cannot be done. is yields the 2 × 1 rectangle remaining (lower le ). Finally, remove a 1 × 1 square from the 2 × 1 rectangle to obtain a 1 × 1 square remaining.