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.

Does this help? https://stackoverflow.com/questions/14002113/how-to-simplify-a-decimal-into-the-smallest-possible-fraction — GrahamTheDev, Aug 06 '20 at 07:33
so to be clear (after your edit) you want to find the smallest **common** (I think that is the bit I missed) denominator (or numerator) where the numbers would still fall within the rounding range to 2 significant figures? Do you have a preference of denominator vs numerator? — GrahamTheDev, Aug 06 '20 at 11:29
Yes, nothing was edited in that repect. Whether denominator or numerator: whichever is is simpler (results in a lower number). — Michel de Ruiter, Aug 06 '20 at 12:52
Are you reading from a text file? So are the numbers doubles or strings? I ask because e.g. in JS 2.36*10=23.599999999999998. So in this case I would prefer strings. — maraca, Aug 07 '20 at 01:20

maraca · Accepted Answer · 2020-08-07T10:12:24.447

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])

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

1 Answers1