Generating all rationals (dc)
From LiteratePrograms
theory
This one-liner is a translation of the Haskell algorithm given (and explained) in Jeremy Gibbons, David Lester and Richard Bird (2006). which (unlike the standard algorithm given here in Python) generates elements of without duplication, by effectively feeding the tree of all bitsequences backwards through GCD.
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 +1 −y) 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.
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 |