Setting a maximum demoninator for fractions

[Albert Chan]

There is an easier way to build the test!

gap = |n1/d1 - p/q| = 1 / (q*d1)

If best-convergent to x is half gap or less, pick best-convergent.

|n1/d1 - x| ≤ (1/2) / (q*d1)
|q*(n1 - d1*x)| ≤ 1/2

This half-gap test assumed x between n1/d1 and p/q. It needed confirmation.

We assumed "overshooted" convergent n2/d2 exist, q = (d0+k*d1),   d0 ≤ q < d2
(if n1/d1 is x last convergent, CF code would just return it, never touched the test)

Here, we just proof where (n1*d0 - n0*d1) = 1 (similar proof for -1)

n0/d0 < n2/d2 ≤ x < n1/d1

(n1/d1 - x) ≤ (n1/d1 - n2/d2) = 1/(d1*d2)
(n1/d1 - p/q) = (n1*(d0+k*d1)-(n0+k*n1)*d1)/(d1*q) = 1/(d1*q) > 1/(d1*d2)

For (n1*d0 - n0*d1) = 1, we have p/q < x < n1/d1