Given some rounded numbers, how to find the original fraction?

Question

After asking this question on math.stackexchange.com I figured this might be a better place after all...

I have a small list of positive numbers rounded to (say) two decimals:

 1.15  (can be  1.145 -  1.154999...)
 1.92  (can be  1.915 -  1.924999...)
 2.36  (can be  2.355 -  2.364999...)
 2.63  (can be  2.625 -  2.634999...)
 2.78  (can be  2.775 -  2.784999...)
 3.14  (can be  3.135 -  3.144999...)
24.04  (can be 24.035 - 24.044999...)

I suspect that these numbers are fractions of integers and that all numerators or all denominators are equal. Choosing 100 as a common denominator would work in this case, that would leave the last value as 2404/100. But there could be a 'simpler' solution with much smaller integers.

How do I efficiently find the smallest common numerator and/or denominator? Or (if that is different) the one that would result in the smallest maximum denominator resp. numerator?

Of course I could brute force for small lists/numbers and few decimals. That would find 83/72, 138/72, 170/72, 189/72, 200/72, 226/72 and 1731/72 for this example.

Answer 1

Assuming the numbers don't have too many significant digits and aren't too big you can try increasing the denominator until you find a valid solution. It is not just brute-forcing. Additionally the following script is staying at the number violating the constraints as long as there is nothing found, in the hope of getting the denominator higher faster, without having to calculate for the non-problematic numbers.

It works based on the following formula:

x / y < a / b   if   x * b < a * y

This means a denominator d is valid if:

ceil(loNum * d / loDen) * hiDen < hiNum * d

The ceil(...) part calculates the smallest possible numerator satisfying the constraint of the low boundary and the rest is checking if it also satysfies the high boundary.

Better would be to work with real integer calculations, e.g. just longs in Java, then the ceil part becomes:

(loNum * d + loDen - 1) / loDen

function findRatios(arr) {
    let lo = [], hi = [], consecutive = 0, d = 1
    for (let i = 0; i < arr.length; i++) {
        let x = '' + arr[i], len = x.length, dot = x.indexOf('.'),
            num = parseInt(x.substr(0, dot) + x.substr(dot + 1)) * 10,
            den = Math.pow(10, len - dot),
            loGcd = gcd(num - 5, den), hiGcd = gcd(num + 5, den)
        lo[i] = {num: (num - 5) / loGcd, den: den / loGcd}
        hi[i] = {num: (num + 5) / hiGcd, den: den / hiGcd}
    }
    for (let index = 0; consecutive < arr.length; index = (index + 1) % arr.length) {
        if (!valid(d, lo[index], hi[index])) {
            consecutive = 1
            d++
            while (!valid(d, lo[index], hi[index]))
                d++
        } else {
            consecutive++
        }
    }
    for (let i = 0; i < arr.length; i++)
        console.log(Math.ceil(lo[i].num * d / lo[i].den) + ' / ' + d)
}

function gcd(x, y) {
    while(y) {
        let t = y
        y = x % y
        x = t
    }
    return x
}

function valid(d, lo, hi) {
    let n = Math.ceil(lo.num * d / lo.den)
    return n * hi.den < hi.num * d
}

findRatios([1.15, 1.92, 2.36, 2.63, 2.78, 3.14, 24.04])