Rational Approximation Finder

approx.py

from __future__ import division
from math import pi

def grader(target):
    return lambda (p1, q1), (p2, q2): cmp(abs(target - p1 / q1), abs(target - p2 / q2))

def gcd(a, b):
    # euclid's algorithm
    while a != b:
        if b < a:
            a, b = a - b, b
        else:
            a, b = a, b - a
    return a

def frac(p, q):
    g = gcd(p, q)
    return (p // g, q // g)

def q_for_p(target, p):
    return max(1, int(round(p / target)))

def p_for_q(target, q):
    return int(round(target * q))

def search_p(target, upper):
    upper = upper if q_for_p(target, upper) < upper else p_for_q(target, upper)
    return [frac(p, q_for_p(target, p)) for p in xrange(1, upper)]

def search_q(target, upper):
    upper = upper if p_for_q(target, upper) < upper else q_for_p(target, upper)
    return [frac(p_for_q(target, q), q) for q in xrange(1, upper)]

def approx(target, upper):
    return sorted(set(search_p(target, upper) + search_q(target, upper)), grader(target))

if __name__ == "__main__":
    for _, f in zip(range(21), approx(pi, 178)):
        print("%3d / %2d" % f)