Setting a maximum demoninator for fractions

[Albert Chan]

(10-04-2023 09:00 AM)komame Wrote:  Even for a case like PI with dmax=30,000,000,000; the result is returned instantly.

For dmax in the millions, code may not be numerically discern which fraction is better.
By design, code will pick the smaller denominator (i.e. convergent)

For above example, it picked wrong, semi-convergent is better, but it is hardly noticeable.

X = PI-3 = 0.14159265359 (exactly)
10225711/72219220      ≈ 0.14159265359000000277      -- error ≈ 2.77E-18
417041790/2945363191 ≈ 0.14159265358999999807      -- error ≈ -1.93E-18

Code:

IF DOT([p,q],[d1,-n1])*DOT([p,q,2*x],[d1,n1,-d1*q]) >= 0 THEN p:=n1; q:=d1; END;

If first DOT has trouble getting ±1, it will return 0.0, due to cancellation.
If first DOT has trouble, so with 2nd DOT (x is between n1/d1 and p/q)

DOT([p,q], [d1,-n1])                = (d1*q) * (p/q - n1/d1)
DOT([p,q,2*x], [d1,n1,-d1*q]) = (d1*q) * ((p/q-x) + (n1/d1-x))

First DOT, we can get correct result, but I choose not to:

DOT([p,q],[d1,-n1]) = (-1)^(while loops)

Difference of 2 CF convergents: n2/d2 - n1/d1 = ±1 / (d1*d2)      → d1*n2 - d2*n1 = ±1
Same result if we replace n2/d2 by semi-convergent p/q

Cas> simplify( DOT([p,q],[d1,-n1]) (p=n2-k*n1, q=d2-k*d1) )      → d1*n2 - d2*n1 = ±1