COMPUTING SCIENCE

# On the Teeth of Wheels

# 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:

8 1 –7 |

33 4 –5 |

58 7 –3 |

83 10 –1 |

191 23 0 |

108 13 +1 |

25 3 +2 |

17 2 +9 |

9 1 +16 |

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:

83 10 –1 |

274 33 –1 |

465 56 –1 |

656 79 –1 |

. . . |

. . . |

191 23 0 |

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.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: Quantum Randomness

**Technologue**: The Quest for Randomness

**Computing Science**: Crinkly Curves