Abstract
We derive an algorithm that enables the rationals to be enumerated in two different ways. One way is known, and is called Calkin-Wilf-Newman enumeration; the second is new and corresponds to a flattening of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Calkin-Wilf-Newman enumeration.
Related
- Slides of my talk at Fun in the Afternoon, in Cambridge: PDF
- Achille Brocot’s original paper “Calcul des rouages par approximation, nouvelle methode”, published in 1861 in “Revue Chronometrique. Journal des horlogers, scientifique et pratique” is available through Google books! You can read the journal or you can download it as a PDF (Brocot’s paper goes from page 208 to 216 of the PDF file)
History
- 17 July 2008: presented at MPC ‘08
- 12 March 2008: accepted for publication at MPC ‘08
- 09 January 2008: submitted to MPC ‘08
- 20 November 2007: rejected for publication in the journal American Mathematical Monthly
- 17 May 2007: I have presented the algorithm at Fun in the Afternoon, in Cambridge
- 30 April 2007: submitted to the journal American Mathematical Monthly
- 22 February 2007: first version of the paper
Computer Scientist
My research interests include software reliability, software verification, and formal methods applied to software engineering. I am also interested in interactive storytelling. For more details, see some of my projects or my selected (or recent) publications. More posts are available in my blog. Follow me on Twitter or add me on LinkedIn.