fraction between 2 number, minimum denominator

[Albert Chan]

(09-16-2023 07:47 PM)Albert Chan Wrote:  Cas> frac_between(18/10,18/10) --> 9/5

Cas> frac_between(1.8, 1.8) practically hang the emulator.

Cas 48 bits float('1.8') = hexfloat(0x1.cccccccccccc) < 9/5

C:\> spigot -C 0x1.cccccccccccc
1/1
2/1
7/4
9/5
126663739519795/70368744177664

Because of rounding errors, d_convergent(1.8, 1.8, 1,0) only return [1,4], d nowhere close enough.

The trick (for float) is to use mod: n/d = floor_div(n,d) + floor_mod(n,d)/d
First term is CF coef, and we simply flip RHS fraction for others.

If n≥0, d>0, (euclidean_mod = floor_mod = trunc_mod), and trunc_mod is *exact*
see Eli Bendersky's blog, Computing remainders by doubling, recursive steps are exact.

Unfortunately, Cas does not have mod for float. We use Lua to illustrate.
Although we work with float, d convergents are exact. No fudge factor is needed.

Code:

function d_convergent(a,a2, b,b2, d,d2) -- 0 <= (a/a2) <= (b/b2)
    local a0, b0 = a, b
    a, b = a%a2, b%b2 -- map a/a2 to a0+a/a2
    a0, b0 = (a0-a)/a2, (b0-b)/b2 -- CF coef
    d = d + a0*d2
    if a == 0   then return d2, d-d2 end
    if a0 ~= b0 then return d2, d end
    return d_convergent(b2,b, a2,a, d2,d)
end

Code:

function frac_between(a,b)      -- assumed non-negative a,b
    if a>b then a,b = b,a end   -- 0 <= a <= b
    local d, d2 = d_convergent(a,1, b,1, 1,0)
    repeat d = d+d2 until (a*d) <= floor(b*d)
    return ceil(a*d), d
end

lua> x = 0x1.cccccccccccc -- = Cas float("1.8")
lua> d_convergent(x,1, x,1, 1,0)
5      70368744177659
lua> frac_between(x,x) -- = fraction(x)
126663739519795      70368744177664

lua> frac_between(0.999999999977, 0.999999999978)
43478173323      43478173324

Lua only see binary float, not decimal (*) In that sense, above fraction is correct.

To reduce decimal to binary conversion error, instead of (a,b), lets do (1-a, 1-b)
Note: numbers have 10 9's after decimal point.

lua> frac_between(0.23E-10, 0.22E-10)
1      43478260870

Or, we enter (a,b), but input as actual fraction, to remove conversion error.

lua> d_convergent(999999999977,1E12, 999999999978,1E12, 1,0)
1      43478260869

First d semi-convergent = 1 + 43478260869 = 43478260870

(*) I do have Decimal/Fraction version, lua + qmath

C:\>run frac_between.lua 0.999999999977 0.999999999978
43478260869/43478260870

C:\>run frac_between.lua 10/7 13/9
10/7