Recounting the Rationals: Twice!

From AcaWiki
Revision as of 14:12, 7 October 2009 by Jff (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Citation: Roland Backhouse, Joao F. Ferreira (2008) Recounting the Rationals: Twice!. Mathematics of Program Construction, LNCS 5133 (RSS)


Tagged: Computer Science (RSS) algorithm enumeration rationals stern-brocot program construction mathematics (RSS)


This paper shows the derivation of an algorithm that enables the positive 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.