Approximate Fraction Matching

Goal. We need to compare a fraction \frac{a}{b} < t where 0 \leq a \leq b \leq 12\,800 and t\in[0,1]. We want to approximate t by a fraction \hat{t} = \frac{c}{d \cdot p} where p = 65\,519 and d \cdot p < 2^{32}.

The approximation error is the maximum observable discrepancy.

\max \vert \frac{a}{b} - \hat{t} \vert

Question. What are the optimal values of c and d, such that

Without loss of generality we can assume t \in F_n, as we can always round t up to the nearest value (and handle t=1 as a special case) without affecting the comparison.

Farey Sequences

Consider all distinct fractions in [0,1] with denominators up to n. When ordered these form the Farey seqeunce of order n, the values of which are:

F_n = \left\{ (a,b) \mid 0 ≤ a ≤ b ≤ n ∧ \gcd(a,b) = 1 \right\}

Some interesting results are known, for example

\vert F_n \vert = 1 + \sum_{i\in[1,n]} φ(i)

where φ is Euler's totient function. There is also a surprisingly simple algorithm to generate the sequence:

def farey_sequence(n, descending = False):
    a, b, c, d = (1, 1, n - 1, n) if descending else (0, 1, 1, n)
    yield (a, b)
    while 0 <= c <= n:
        k = (n + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
        yield (a, b)