Python Cookbook

Converting Numbers to Rationals via Farey Fractions

Credit: Scott David Daniels

Problem

You have a number v (of almost any type) and need to find a rational number (in reduced form) that is as close to v as possible but with a denominator no larger than a prescribed value.

Solution

Farey fractions, whose crucial properties were studied by Cauchy, are an excellent way to find rational approximations of floating-point values:

def farey(v, lim):
    """ No error checking on args. lim = maximum denominator.
    Results are (numerator, denominator); (1, 0) is "infinity".
    """
    if v < 0:
        n, d = farey(-v, lim)
        return -n, d
    z = lim - lim    # Get a "0 of right type" for denominator
    lower, upper = (z, z+1), (z+1, z)
    while 1:
        mediant = (lower[0] + upper[0]), (lower[1] + upper[1])
        if v * mediant[1] > mediant[0]:
            if lim < mediant[1]: return upper
            lower = mediant
        elif v * mediant[1] == mediant[0]:
            if lim >= mediant[1]: return mediant
            if lower[1] < upper[1]: return lower
            return upper
        else:
            if lim < mediant[1]: return lower
            upper = mediant

For example, farey(math.pi, 100) == (22, 7).

Discussion

The rationals resulting from this algorithm are in reduced form (numerator and denominator mutually prime), but the proof, which was given by Cauchy, is rather subtle (see http://www.cut-the-knot.com/blue/Farey.html).

Note the trickiness with z. It is a zero of the same type as the lim argument. This lets you use longs as the limit if necessary, without paying a performance price (not even a test) when there’s no such need. ...