American Scientist

For many years, the basic raw material of the computer industry was not silicon but brass. The calculators of Wilhelm Schickard, Blaise Pascal and Gottfried Wilhelm Leibniz were all based on the meshing of metal gears. Later, Charles Babbage conceived elaborate fantasies of gearwork for his calculating engines. Later still, Vannevar Bush put gears and other rotating parts at the heart of his differential analyzer. And all of these inventors were foreshadowed by anonymous artisans in the city of Rhodes in the first century B.C., who assembled more than 30 gears in a remarkable calendrical computer known as the Antikythera mechanism.

These examples testify to the importance of gears in the history of computing. Less obvious is the importance of computing in the history of gears. I was ignorant of the connection myself until quite recently, when I went looking in the library for a work on number theory and found myself making a detour into the engineering shelves. I learned there that the designers of gear trains have not merely borrowed ideas from mathematics but have also developed some of those ideas on their own and lent them back to the mathematicians. Mechanical engineers doubtless know all about this two-way traffic between math and mechanism, but others may find the computational roots of gear design as surprising as I did.

The Stern-Brocot Tree

The story begins a year ago, when I was writing in this space about the work of Divakar Viswanath (now at the University of Chicago) on a randomized version of the Fibonacci numbers. In the ordinary Fibonacci sequence (1, 1, 2, 3, 5, 8, 13,...) you form each term by adding the two previous terms. In the "Vibonacci" series, you either add or subtract, with each operation chosen at random. You might guess that random additions and subtractions would tend to cancel each other out, but Viswanath proved that the terms grow steadily in absolute value.

Viswanath’s proof makes use of an object from number theory called the Stern-Brocot tree, which is constructed as follows. Take any two rational numbers, a/b and c/d, and insert between them a third value, called the mediant, equal to (a+c)/(b+d). For example, starting with 2/3 and 3/4 yields the mediant (2+3)/(3+4), or 5/7. Now, with three numbers in hand, construct mediants between the first and second and between the second and third, so that the next level of the tree has five members. The process can continue indefinitely. Note that on each level the numbers are always in order.

The canonical version of the Stern-Brocot tree starts with the numbers 0/1 and 1/0. (The second of these "numbers" is admittedly peculiar; somebody has said it is "infinity reduced to lowest terms.") With these starting values, the second level of the tree consists of 0/1, 1/1 and 1/0, and the third level becomes 0/1, 1/2, 1/1, 2/1 and 1/0. (See Figure 2.) The remarkable thing about the tree is that every rational number appears somewhere among its leaves, but no number appears more than once.

When I described the Stern-Brocot tree in my earlier article, I mentioned that it is named for "the mathematician Moriz Stern and the watchmaker Achille Brocot." Now I must make a confession. Although Viswanath's paper cited the works of Stern and Brocot, I did not look up those references. At the time, I excused this lapse of diligence on the grounds that Viswanath himself gave a lucid account of the tree's construction, and I also had an excellent secondary source, namely the textbook Concrete Mathematics, by Ronald L. Graham, Donald E. Knuth and Oren Patashnik. I knew what I needed to know of the tree without tracking down two obscure 19th-century papers written in German and French. Or I thought I knew. In fact I didn't know what I was missing.

The Professor and the Watchmaker

Thus the situation might have remained but for the prompting of a friend and longtime reader of this department, Horacio A. Caruso of La Plata, Argentina. Caruso and his colleague Sebastián M. Marotta were sufficiently interested in the Vibonacci phenomenon to undertake investigations of their own. For example, they applied the Vibonacci algorithm to complex numbers, creating an intriguing series of fractal images. When Caruso inquired about the works of Stern and Brocot, I was belatedly inspired to go look them up.

Stern's paper was not hard to find. Moritz Abraham Stern (my earlier spelling Moriz was erroneous) was a prominent figure in the mathematical world of his day, a colleague of Carl Friedrich Gauss who succeeded Gauss as Ordinary Professor of Mathematics at the University of Göttingen. According to Peter Pulzer, Stern was "the first Jew to be appointed to a full professorship at a German university without first converting to Christianity."

Stern's paper appeared in the Journal für die Reine und angewandte Mathematik, also known as Crelle's Journal, after its first editor, August Leopold Crelle. When the journal was founded in 1826, its title reflected the growing division in mathematics between Reine and angewandte—"pure" and "applied." Stern's paper, "On a number-theoretical function," is of the pure persuasion. He discusses several versions of the procedure for forming mediants and relates the sequence of mediants to other ways of constructing the set of rational numbers, such as continued fractions. Nowhere does he hint that his number-theoretical function might be of use to the makers of gears.

Finding Brocot's contribution was more challenging. His article was published in the Revue Chronométrique, a French journal that commenced publication in 1855 and ceased in 1914. Only when I began searching for the Revue did it occur to me to wonder why a work on number theory was appearing in a clockmakers' journal.

None of the libraries within easy reach had the Revue Chronométrique, but a catalogue search at Duke University did return one hit for the term "Brocot." I was referred to a 1947 work by Henry Edward Merritt, titled Gear Trains: Including a Brocot Table of Decimal Equivalents and a Table of Factors of All Useful Numbers up to 200,000. A Brocot table? Useful numbers? What was this all about? I walked from the mathematics library to the engineering library next door and soon had a worn blue volume in my hands. When I opened to the preface, I knew I would have to read the rest of the book. Merritt begins:

Prefaces are not what they were. Who could resist the opening phrases of the editor's preface to the second edition of Camus on the Teeth of Wheels, published in 1836—

"Always feeling annoyed at meeting with a long preface to a book, labouring as it were to beget a prepossession in favour of the author, and standing between the reader and the subject, like an impertinent porter, who detains a visitor at the gate, instead of giving him admission to the presence of the master, the editor will confine himself to five pages of preliminary remarks...."

Indeed, who could resist? And, furthermore, what is this mysterious Camus on the Teeth of Wheels? The title would have been an apt one for the tormented existentialist Albert Camus, but it comes from the wrong century.

Counting Teeth

Reading on in Merritt's book, I soon learned why aspects of number theory have attracted the interest of gear makers. Here is an example of the basic problem. Suppose you have a shaft that turns once per minute, and you want to design gears that will slow this motion to one revolution per day, which works out to a speed ratio of 1,440 to 1. The first law of gearwork says that the speed of a gear is inversely proportional to the number of its teeth. Thus the most direct solution would be a driving gear (a pinion) with just one tooth, meshing with a driven gear (or wheel) of 1,440 teeth. But a one-tooth gear would be extremely awkward, and a 1,440-tooth gear is inconveniently large. You could solve the problem of the too-small pinion by multiplying both sides of the ratio by some convenient number, say 10. You would then have a pinion of 10 teeth, but of course the already-too-large wheel would be even larger, with 14,400 teeth.

The answer to this quandary is a compound gear train, where two or more pairs of mating gears progressively reduce the rotational speed. In a two-stage train, a pinion a meshes with a wheel A; then a second pinion b, mounted on the same shaft as A, turns wheel B. The overall gear ratio is a/A x b/B, and so you can choose any convenient values of a, A, b and B that yield the correct product. For example, compound gears with the ratios 6/200 and 5/216 form the product 30/43200, which reduces to the required 1/1440. If wheels of 200 and 216 teeth are still too large, then a three-stage train with ratios of 6/72, 6/60 and 5/60 would yield the same result. (I ignore the fact that each pair of gears reverses the sense of rotation.)

The next question is: Where do numbers like 6/200 and 5/216 come from? It's easy to verify that they produce the correct ratio, but how do you find such numbers in the first place? The answer comes straight from number theory: factoring. In the ratio 30/43200, the numerator has the prime factors 2x3x5, and the denominator breaks down into eleven factors: 2x2x2x2x2x2x3x3x3x5x5. The Fundamental Theorem of Arithmetic guarantees that no matter how you group these factors, their product will always be the same. The factors of the numerator can be partitioned into two groups in just three ways: 6x5, 3x10 and 2x15. The factors of the denominator 43,200 can be partitioned into two groups in 41 distinguishable ways.

This application of factoring explains the presence in Merritt's book of a "table of factors of useful numbers up to 200,000." The "useful" numbers turn out to be those whose largest factor is no greater than 127, which Merritt suggests is a reasonable upper limit for the number of teeth on a gear. Number theorists have another word for the same concept: Integers that have many small factors are called "smooth" numbers.

Does the need to factor numbers make the design of compound gear trains a hard computational problem? Factoring has an enigmatic status in computer science: For conventional computer hardware, the only known factoring algorithms are inefficient, and therefore slow in the worst case, but no one has proved that better algorithms cannot exist. For gear design, however, the issue of algorithmic intractability simply does not arise, because the factoring of smooth numbers is always easy. Even the crudest algorithm—trial division—works quickly with numbers that have only small factors.

Gear Geeks

Converting minutes into days is a problem that gears can solve exactly, but what if the ratio of two speeds is π? Here the first law of gearwork fails because it runs up against the zeroth law—that the number of teeth on a gear must be an integer. No ratio of integers can be equal to π. The best one can hope for is a good rational approximation. This is where Merritt's "Brocot table" enters the story, and it put me back on the trail of Brocot's original paper.

A visit to the New York Public Library proved tantalizing; I found several volumes of the Revue Chronométrique, but not the volume I needed. On the other hand, the library was able to supply the enigmatic Camus on the Teeth of Wheels. Camus turned out to be Charles-Étienne-Louis Camus, 1699–1768, author of a Cours de Mathématique published in 1749. The section of this textbook dealing with gearwork was extracted and translated into English by John Isaac Hawkins, a civil engineer, and published under the title A Treatise on the Teeth of Wheels, Demonstrating the Best Forms Which Can Be Given to Them for the Purposes of Machinery; Such as Mill-work and Clock-work, and the Art of Finding Their Numbers.

The first part of Camus's treatise deals with a geometrical rather than a number-theoretical question: What is the ideal shape for a gear tooth? This issue engaged the talents of mathematicians and other savants for generations. Robert Hooke, Thomas Young, Leonhard Euler and Josiah Willard Gibbs all debated the merits of epicycloids and involutes. It's a fascinating problem, but I turned to Part II of the treatise, where Camus takes up the numerical aspects of gear design.

For cases where an exact solution is possible, Camus explains the method of reducing a number to its prime factors and then partitioning the factors into as many groups as there are pairs of gears. He then turns to the task of approximating a ratio when the numbers have no convenient factorization. As an example he offers this problem: "To find the number of the teeth...of the wheels and pinions of a machine, which being moved by a pinion, placed on the hour wheel, shall cause a wheel to make a revolution in a mean year, supposed to consist of 365 days, 5 hours, 49 minutes." Multiplying out the days and hours yields a target ratio of 720/525949. The numerator of this fraction factors conveniently, but the denominator is a prime. Thus the aim is to find another fraction, as close as possible in value to 720/525949, but with both a numerator and a denominator that have small factors. Camus remarks: "In general this is done by repeated trials; but as this method is defective, we shall here propose another, by which the problem may be solved with more certainty."

But the next 20 pages, which set forth the method through worked examples, leave the impression that it's hardly much better than trial and error. Camus's procedure for finding ratios close to the target is a fairly arduous algebraic process, made worse by awkward and verbose notation. Furthermore, trial-and-error is still required, because there is no guarantee that a ratio generated by the method will be factorable. Camus reports seven failures before he hits on the ratio 196/143175, which can be factored as 4/25 x 7/69 x 7/83. It was Brocot, a century later, who found a better way.

An Eminent Maker

I finally tracked down Brocot's memoir in the Revue Chronométrique at the Mariners' Museum Library in Newport News, Virginia. (It, is not such an unlikely place to go looking, given the close connections between seafaring and horology.) The library staff were able to help me find the article even though the citations I was working from turned out to have errors in both the volume number and the date.

A reference work on clockmakers lists Achille Brocot as "an eminent maker" and mentions his mechanical contrivances, such as the Brocot escapement, but it says nothing of contributions to mathematics. The article in the Revue Chronométrique sticks to practicalities; the aim is to build a gear train, not to construct the infinity of rational numbers. And yet if theory is not emphasized, there is nonetheless something distinctly modern here. Brocot presents his method as an algorithm, albeit one adapted to pencil-and-paper methods rather than to programmable machinery.

As a pedagogical example, Brocot invents the problem of gearing a shaft that turns once in 23 minutes to another shaft that completes a revolution in three hours and eleven minutes, or in other words 191 minutes. Because 23 and 191 are both primes, gears with fewer teeth can only approximate the true ratio. To find the best such approximations, Brocot begins by noting that 191/23 is greater than 8 but less than 9, so that the ratio must lie somewhere in the interval between 8:1 and 9:1. Accordingly, he writes in a row at the top of a sheet of paper:

Here the first two numbers represent the ratio 8:1, and the third number is the error associated with this initial approximation. The error is –7 because a ratio of 8/1 is equal to 184/23 rather than 191/23, so that the slower wheel would complete its revolution seven minutes early.

At the bottom of the same page, Brocot writes:

Again the first two numbers are an approximation to the ratio, and the third number is an error term, indicating that gears in a 9:1 ratio will take 16 minutes too long to complete a revolution, since 9/1 is equal to 207/23.

Now the iterative part of the algorithm begins. Brocot adds the numbers in all three columns and writes the row of sums in the middle of the page:

This result is a new and more refined approximation. At a ratio of 17:2, turning the faster shaft in 23 minutes causes the slower shaft to complete a revolution in 195.5 minutes, for an error of four and a half minutes. In the table, the error term of +9 is understood to represent the quantity 9/2.

Brocot now has the choice of adding the middle row of numbers to those at the top of the page or to those at the bottom. The mediant between top and middle is preferable because it reduces the error term. The result is another row:

With this ratio the slower wheel turns in 191.67 minutes, for an error of two-thirds of a minute.

Further approximations are constructed in the same way, always adding the latest entry to whichever of its neighbors reduces the error term. The method is deterministic, with no need for guesswork or trial and error. And, like any good algorithm, it is sure to terminate eventually. The end comes when the process converges on the original ratio 191/23, which necessarily has an error of zero. The final state of the table looks like this:

The two columns at the left, read as numerators and denominators of rational numbers, make up a small section of the complete Stern-Brocot tree.

Brocot's algorithm reveals that the closest approximations to 191/23 are ratios of 83/10 (which runs a tenth of a minute fast) and 108/13 (a thirteenth of a minute slow). To do better requires a multistage gear train. Surprisingly, Brocot applies exactly the same algorithm to the design of such trains. He places one of the approximations at the top of the page and the exact ratio at the bottom. Then a series of additions produces successive ratios with smaller errors and larger numbers of teeth:

But now trial-and-error does enter the process, because it is necessary to find one of the approximations where both the numerator and the denominator can be factored conveniently. In this case, the third entry in the table can be factored as 5/7 x 93/8, yielding a train of four gears that approaches the correct speed to within a 56th of a minute.

Brocot's algorithm can be employed as needed to find approximations to any given ratio, but Brocot also recognized that all the computation could be done beforehand and the results compiled into a table. This is the Brocot table included in Merritt's book; it is essentially a list of all fractions with numerator and denominator no greater than 100, ordered according to magnitude.

Shifting Gears

Just as Stern mentions no practical applications of his number-theoretical function, Brocot gives little attention to the mathematical foundations of his gear-train algorithm. (In a longer essay, which I have still not been able to lay hands on, Brocot claims to provide more theoretical background.) There is no sign that either man knew of the other's work. After the fact, however, connections between them are easy to see; they are doing the same thing but describing it differently.

There is even a connection between Brocot's algorithm and the Fibonacci series, where this whole quest began. To see the relation, just try using Brocot's method to find ratios approximating the constant known as phi, or the golden ratio, an irrational number with a value of approximately 1.618. The series of approximants begins 1/1, 2/1, 3/2, 5/3, 8/5, 13/8,.... Hidden within these ratios is the complete sequence of Fibonacci numbers.

Working through examples of Brocot's process by hand, and leafing through the pages of the printed Brocot table, leaves me feeling wistful and uneasy. The ingenuity and diligence on exhibit here are certainly admirable, and yet from a modern point of view they are also tinged with a horrifying futility. I am reminded of those prodigies who spent years of their lives calculating digits of the decimal expansion of π—a task that is now a mere warmup exercise for computer software. I cannot help wondering which of my own labors will appear equally quaint and pathetic to some future reader who ransacks libraries for old volumes of American Scientist.

The fact is, the design of simple gear trains is no longer a computationally interesting problem, because computation itself has overwhelmed it. With so much calculating power at your fingertips, it's hardly worth the bother of being clever. You can solve gearing problems by brute-force, using methods that would have been unthinkable for Camus or Brocot, or even for Merritt, who was writing hardly more than 50 years ago. If you need to approximate some ratio, just have the computer try all pairs of gears with no more than 100 teeth. There are only 10,000 combinations; you can churn them out in an instant. For a two-stage compound train, running through the 100 million possibilities is a labor of minutes.

The whirling gears of progress have put the gearmakers out of work.

© Brian Hayes