Generating all rationals (Python)

From LiteratePrograms

Other implementations: C | dc | Haskell | Python

Generating Q from N²

We will first generate the non-invertible elements of the rationals (), then follow with the remainder of .

<<generate rationals>>=
def generate_rationals():
    """ generates each rational once, coded in a tuple: (i,j) = i/j"""
    generate non-invertible rationals
    generate invertible rationals

The non-invertible elements are trivial:

<<generate non-invertible rationals>>=
yield (0,1)

In order to generate the invertible elements, we use a diagonal construction, similar to the one in used in Generating all integer lattice points (Python) for . Now we wish to generate ascending diagonals, so we will count n up indefinitely, generating a diagonal for each value of n.

<<generate invertible rationals>>=
n = 0
while True:
    generate diagonal entries
    n += 1

The diagonal itself merely generates each formal rational whose numerator and denominator add up to n + 1. For instance, when n = 6, we will generate .

<<generate diagonal entries>>=
for m in xrange(n):
    (i,j) = (m+1,n-m)
    filter for uniqueness

Unlike the problem of generating lattice points, in which for instance (1,2) and (2,4) would code for different screen pixels, we find that two formally different rational expressions can be equivalent: . Therefore we calculate the greatest common denominator and use the resulting flag to select only the fully reduced fractions.

<<filter for uniqueness>>=
if gcd(i,j) == 1:
    yield (i,j)
    yield (-i,j)

finishing up

finally, we must lift an implementation of GCD from Category:Euclidean algorithm

<<gcd>>=
def gcd(a,b):
        """ the euclidean algorithm """
        while a:
                a, b = b%a, a
        return b

and produce some simple output.

<<allrats.py>>=
gcd
generate rationals
if __name__ == "__main__":
        for (i,j) in generate_rationals():
                print "%d/%d" % (i,j)

Once this program finishes running, in principle one could compare the output against a list of the rational numbers to verify that it worked properly. For reasons of space (and patience!), this test case has been omitted.

even better algorithm

Based on rats8 from http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf

def generate_rationals2():
    yield (0,1)
    (n,d) = (1,1)
    while True:
        yield (n,d)
        yield (-n,d)
        (q,r) = divmod(n,d)
        (n,d) = (d,(q+1)*d-r)

Download code