Generating all rationals (dc)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | dc | Haskell | Python

[edit] theory

This one-liner is a translation of the Haskell algorithm given (and explained) in Jeremy Gibbons, David Lester and Richard Bird (2006). Enumerating the Rationals. which (unlike the standard algorithm given here in Python) generates elements of \mathbb{Q} without duplication, by effectively feeding the tree of all bitsequences backwards through GCD.

[edit] practice

<<allrats.dc>>=
1sn1sd[lnn[/]Pldn[ ]Plnld~sasbldsnlb1+ld*la-sdlRx]dsRx

The Haskell is a little less opaque, and goes as follows:

rats7 :: [ Rational]
rats7 = iterate next 1
next x = recip (fromInteger n +1y) where (n, y) = properFraction x 

where

  • ln ld ~ sa sb roughly corresponds to (n, y) = properFraction x ,
  • ld sn lb 1+ ld* la - sd to recip (fromInteger n + 1 -y)
  • and 1sn 1sd to the 1 in iterate next 1.

for an explanation of why this works, please consult the Gibbons paper.

[edit] wrapping up

Unfortunately the dc on my system is not properly tail-recursive and so fails to generate all the rationals. Also, it insists upon printing out escaped newlines from time to time.

Both of these issues can be mitigated by using the Desk calculator (Python) emulator, or avoided entirely by calling dc with the following command line:

(echo "1sn1sd"; yes "lnn[/]Pldn[ ]Plnld~sasbldsnlb1+ld*la-sd") | dc | unvis

producing a string that starts with:

1/1 1/2 2/1 1/3 3/2 2/3 3/1 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1 1/5 5/4 4/7 7/3 3/8 8/5 5/7 7/2 2/7 7/5 5/8 8/3 3/7 7/4 4/5 5/1 1/6 ...
Download code
hijacker
hijacker
hijacker
hijacker