Recounting the Rationals: Twice!
in terms
- Citation:
- Backhouse R, Ferreira JF. 2008. Recounting the Rationals: Twice!. Mathematics of Program Construction (LNCS 5133).
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.
Citation Key:
1864DOI:
10.1007/978-3-540-70594-9_6
Tags
- .NET (1)
- algorithms (2)
- autosar (1)
- C# (1)
- Calkin-Wilf tree (1)
- concurrency (1)
- CS education (1)
- cyclotomic game (1)
- deadline (1)
- Eisenstein array (1)
- Embedded Systems (1)
- fences (1)
- freertos (2)
- Giotto (1)
- Hoare triples (1)
- invariant (2)
- invariants (3)
- JaSkel (1)
- Java (1)
- linear logic (2)
- logic (2)
- mathematics (1)
- MathIS (1)
- nuclear pennies (1)
- number theory (2)
- parallelism (1)
- polynomials (1)
- rational number (2)
- rational numbers (1)
- separation logic (2)
- Simulation (1)
- Solitaire (2)
- storytelling (2)
- structure editor (1)
- tablet PCs (1)
- teaching (3)
- tiling problems (2)
- Timed CSP (1)
- type isomorphism (1)
- verification (4)
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.