Companion program for Joe Horn’s continued fractions article

[Albert Chan]

Perhaps a simple linear search?
Denominator to seek normally small anyway.
Because we never skip, denominator guaranteed smallest!

This has the advantage of only needing fast float. (It is hard to get exact CF coefs. with float)

Code:

function frac_between(a,b)
    if a>b then a,b = b,a end
    local d = 1
    while (a*d) > floor(b*d) do d=d+1 end
    return ceil(a*d), d
end

lua> frac_between(3.1415, 3.1416)
333      106
lua> frac_between(1.8, 1.9)
9      5
lua> frac_between(1.8, 1.8)
9      5
lua> frac_between(1.8, 1.7)
7      4
lua> frac_between(1.8, 1.6)
5      3
lua> frac_between(1.8, 1.5)
3      2
lua> frac_between(-pi, -pi*.99)
-25      8

Update: ceil(a*d) <= floor(b*d) test simplified to (a*d) <= floor(b*d)