Recounting the Rationals: Twice!

From AcaWiki
Jump to: navigation, search


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



Download: http://www.joaoff.com/publications/2008/rationals

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


Summary:

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.