an error while trying to find fraction lua

Question

local function FindFraction(float)
    local i,f = math.modf(float)
    local result = 1 / f % 1 == 0 and '1 / ' .. math.floor(1 / f) or f == 0 and i or nil
    if not result then 
        for k = 1, 10000 do 
            if 1 / f * k % 1 == 0 then 
                result = tostring(k + i .. ' / ' .. 1 / f * k)
                break 
            end
        end 
    end
    return float > 1 and i .. ' + (' .. result .. ')' or result
end 
print(FindFraction(0.1)) -- 1 / 10
print(FindFraction(0.2)) -- 1 / 5
print(FindFraction(0.3)) -- 3 / 10
print(FindFraction(0.4)) -- 2 / 5
print(FindFraction(0.5)) -- 1 / 2
print(FindFraction(0.6)) -- 3 / 5
print(FindFraction(0.7)) -- 7 / 10 
print(FindFraction(0.8)) -- 8 / 10 
print(FindFraction(0.9)) -- 9 / 10 
print(FindFraction(1)) -- 1
print(FindFraction(1.1)) -- nil or error ( what is wrong here? )

it works well sometimes like .234 is 117 / 500 but sometimes it straight errors because the result is nil

tried everything i could, nothing helped

Edit: thanks guys i just found out the problem and solved it by adding f = tonumber(string.format('%g',string.format('%.'..(10)..'f',f))) on the 3rd line!

Answer 1

Ivo explained how the problem stems from float precision issues: A number like 1.1 isn't stored as exactly (the fraction) 11/10. You can see rounding errors by formatting using more digits of precision than Lua uses by default:

> ("%.17g"):format(1.1)
1.1000000000000001

However, under the hood, floats are effectively just fractions with a fixed denominator. We can extract mantissa and exponent from floats using math.frexp:

Returns m and e such that x = m2^e, e is an integer and the absolute value of m is in the range [0.5, 1) (or zero when x is zero).

This allows us to extract the exponent, leaving us with the mantissa. The mantissa of a 64-bit float has 52 bits plus one implicit bit. Thus if we multiply by 2^53, we are guaranteed to get an integer. Since this is just a multiplication with a power of two, all it does under the hood is increment the exponent.

local function FindFraction(float)
    local m, e = math.frexp(float)
    local denom = 2^53
    local num = m * denom
    if e < 0 then
        denom = denom * 2^-e
    else
        num = num * 2^e
    end
    return ("%d/%d"):format(num, denom)
end

for _, float in ipairs{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 1.1} do
    print(float, FindFraction(float))
end

This produces ugly, but accurate fractions representing the floats:

0.1 7205759403792794/72057594037927936
0.2 7205759403792794/36028797018963968
0.3 5404319552844595/18014398509481984
0.4 7205759403792794/18014398509481984
0.5 4503599627370496/9007199254740992
0.6 5404319552844595/9007199254740992
0.7 6305039478318694/9007199254740992
0.8 7205759403792794/9007199254740992
0.9 8106479329266893/9007199254740992
1   9007199254740992/9007199254740992
1.1 9907919180215092/9007199254740992

This currently makes no effort to shorten the resulting fractions by dividing both numerator and denominator by the GCD of the two; perhaps you will want to take a look at this Lua fraction implementation I wrote for that. Note that you will ultimately end up with fractions which use numerators and denominators which may not afford to lose precision. If you want fraction operations to always work exactly, you'll have to use big integers for numerator and denominator.

Answer 2

The problem is that

if 1 / f * k % 1 == 0 then

gives false for all k in this situation.

The error is because of floating point precision. Consider this code:

local i,f = math.modf(1.1)
print(i,f)
print(f - 0.1)

This first print gives as expected

1   0.1

But the second print does not return 0 but actually

8.3266726846887e-17

I'm not sure how you could solve this but maybe this points you in the right direction.

Answer 3

guys i rewrote the code and now it works well with everything up to 6 digits and integers here it is:

local function FindFraction(float)
    local int, float = math.modf(float)
    if float == 0 then return int end
    float = string.format('%g',float)
    local function ReduceFraction(numerator,denominator)
        local n, m = numerator, denominator
        while m ~= 0 do 
            n, m = m, n % m 
        end 
        return numerator/n .. ' / ' .. denominator/n 
    end
    local digits = float:sub(float:find('.')+2,#float)
    local numerator, denominator = tonumber(digits), 10 ^ #digits
    return int > 1 and int .. ' + ('..ReduceFraction(numerator,denominator)..')' or ReduceFraction(numerator,denominator) 
end