(12C) Decimal to Fraction

[Albert Chan]

I removed \(0 < x < 1\) restriction of farey fraction.

Code:

>>> farey(0.10322, 1e8)   # fractions match, stop
(5161, 50000)
>>> farey(-0.10322, 1e8)  # negatives ok
(-5161, 50000)
>>> farey(1/pi, 700)      # pick the best estimate
(113, 355)
>>> farey(pi, 100)        # abs(x) > 1 ok
(311, 99)
>>> farey(3, 100)         # integer ok
(3, 1)

Code:

def farey(x, limit=100):
    'return Farey fraction (n,d) closest to x with denominator <= limit'
    n1, d1 = int(x), 1      
    if n1 == x: return n1, d1
    if x < 0: n1 -= 1       # lo = floor(x)
    n2, d2 = n1+1, 1        # hi = lo + 1
    while 1:
        n, d = n1 + n2, d1 + d2
        if d > limit: break
        if   x * d > n: n1, d1 = n, d
        elif x * d < n: n2, d2 = n, d
        else: return n, d   # exact match
    pick_hi = (n2/d2 - x) < (x - n1/d1)
    return (n2, d2) if pick_hi else (n1, d1)