Approximate rational fractions using convergents of the continued fraction expansion

convergents.py

# Returns (exact, p, q) where p/q is an approximation to numer/denom and exact is true if
# the approximation is exact.
def convergent(numer, denom, limit):
    """Find an approximation to numer/denom with neither numerator nor denominator above limit"""
    prev_p, cur_p = 0, 1
    prev_q, cur_q = 1, 0

    rest_p = numer
    rest_q = denom
    while rest_q != 0:
        # The next term of the continued fraction
        int_part = rest_p // rest_q # floor divide!
        rem = rest_p % rest_q # remainder after floor divide

        # Calculate the next convergent incorporating this term
        prev_p, cur_p = cur_p, cur_p * int_part + prev_p
        prev_q, cur_q = cur_q, cur_q * int_part + prev_q
        if abs(cur_p) > limit or cur_q > limit:
            # exceeded our limit, return the previous approximation
            return (False, prev_p, prev_q)

        # Continue expanding the continued fraction for the
        # reciprocal of the remainder that didn't go into int_part
        rest_p, rest_q = rest_q, rem

    # if we got here, we found an exact solution
    return (True, cur_p, cur_q)

print(convergent(-31415926535, 10000000000, 256))
print(convergent(31415926535, 10000000000, 1024))
print(convergent(-31415926535, 10000000000, 1000000000000))
print(convergent(10, -4, 100))