Recounting the Rationals: Twice! Export

@inproceedings{jff*08:rationals, abstract = {We derive an algorithm that enables the rationals to be efficiently enumerated in two different ways. One way is known and is credited to Moshe Newman; it corresponds to a deforestation of the so-called Calkin-Wilf tree of rationals. The second is new and corresponds to a deforestation 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 Newman's algorithm.}, author = {Backhouse, Roland and Ferreira, Jo\~{a}o F.}, booktitle = {Mathematics of Program Construction}, citeulike-article-id = {3049781}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-70594-9_6}, citeulike-linkout-1 = {http://joaoff.com/publications/2008/rationals}, doi = {10.1007/978-3-540-70594-9_6}, journal = {Mathematics of Program Construction}, keywords = {algorithm-derivation, calkin-wilf, jff-bib, stern-brocot}, pages = {79--91}, posted-at = {2008-07-28 11:57:32}, priority = {2}, series = {LNCS}, title = {Recounting the Rationals: Twice!}, url = {http://dx.doi.org/10.1007/978-3-540-70594-9_6}, volume = {5133}, year = {2008} }

TY - CONF ID - jff*08:rationals L3 - citeulike-article-id:3049781 N2 - We derive an algorithm that enables the rationals to be efficiently enumerated in two different ways. One way is known and is credited to Moshe Newman; it corresponds to a deforestation of the so-called Calkin-Wilf tree of rationals. The second is new and corresponds to a deforestation 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 Newman’s algorithm. JF - Mathematics of Program Construction SE - LNCS EP - 91 TI - Recounting the Rationals: Twice! VL - 5133 T2 - Mathematics of Program Construction SP - 79 KW - algorithm-derivation KW - calkin-wilf KW - jff-bib KW - stern-brocot AU - Backhouse, Roland AU - Ferreira, João PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-70594-9_6 ER -