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)
Internet Archive Scholar (search for fulltext): Recounting the Rationals: Twice!
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.


Retrieved from "https://acawiki.org/index.php?title=Recounting_the_Rationals:_Twice!&oldid=2078"