Recounting the Rationals: Twice!

Authors

Roland Backhouse and João F. Ferreira

Downloads

• Paper: PDF [Springer Link]
• Haskell code: AppendixRationals.lhs
• Slides of my talk at Mathematics of Program Construction (MPC '08), in Marseille, France: PDF
• 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)

Status

Published in Mathematics of Program Construction, Springer-Verlag, LNCS 5133, pp. 79—91 (proceedings of the 9th International Conference Mathematics of Program Construction, MPC 2008, Marseille, France, July 15—18, 2008)

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.

Keywords

program construction, calculational method, algorithms

Bibtex entry

@inproceedings{jff*08:rationals,
	title = {Recounting the Rationals: Twice!},
	author = {Backhouse, Roland  and Ferreira, Jo\~{a}o},
	journal = {Mathematics of Program Construction},
        series = {LNCS},
        publisher = {Springer-Verlag},
	pages = {79--91},
	volume = {5133},
	year = {2008},
	url = {http://joaoff.com/publications/2008/rationals},
	doi = {10.1007/978-3-540-70594-9\_6},
	citeulike-article-id = {3049781}
}

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
• 30 April 2007 — submitted to the journal American Mathematical Montly
• 17 May 2007 — I have presented the algorithm at Fun in the Afternoon, in Cambridge
• 22 February 2007 — first version of the paper

v0.1 © JFF 2008