Accounting for floating point error when rounding

Question

I have to implement some business logic that will round a number (typically a double) upwards. Given that this number comes from a third-party and I don't know how they come to calculate it I'm anticipating errors in it. My proposed routine to mitigate rounding errors (like Math.ceil(1.000000000000002) = 2) is as follows:

export const roundupDiscount = (discount: number) => {
    // We have to give advantage to the customer for the discount value when rounding,
    // that is to say, we will sacrifice the penny when we can't be exact. This means
    // we have to always round the discount upwards (so we can't Math.round because
    // half the time we'll round in the wrong direction.)
    // To account for numbers like, say, 1.000000000000002 (i.e. (1 / 5 / 7) * 5 * 7))
    // then we subtract off a "small" number (scaled with the magnitude of discount)
    // which will nudge below the number we will round up to

    if (!discount) return 0 // discount shouldn't be negative

    const magnitude = Math.floor(Math.log(discount) / Math.log(10))
    const epsilon = Math.pow(10, magnitude - 14)
    return Math.ceil(discount - epsilon)
}

Given that a double has between 15-17 significant digits in it, I'm choosing epsilon, arbitrarily, such that I have a couple of trailing digits to play with.

Can anybody spot any cases where this is going to get things wrong? simplify this thing, or, given this is node.js point me towards an npm module that does this kind of thing for me?

Note: I have to get this past code-review at work so I'd much prefer if there was a good library out there that I can use instead and not even bother submitting this!

Answer 1

Discovered this needs rework

Testing this with small numbers shows that for all practical purposes, this function is broken. I'd like roundupDiscount(Number.EPSILON) to be 0 (which could come about from subtracting two numbers meant to be equal, but differing by an error (similar to the classic (0.1 + 0.2) - 0.3)).

However for a number like Number.EPSILON its value, including significant digits, is 0.000000000000000222044604925031, and so the computed epsilon here being 10e-28 is way too small to have any effect. This function only really works when the integer part > 0

It can be corrected in this respect by clamping the magnitude at 0 but I think I'll have a battle to convince anyone this should go into our codebase ...

Updated implementation:

export const roundupDiscount = (discount: number) => {
    // Given that discount is "sensible", if it is equal to some integer x plus a
    // small positive error component, then it must return x. Otherwise it must
    // return Math.ceil(discount)
    
    if (discount < 0 || discount > Number.MAX_SAFE_INTEGER) return discount
    if (discount < Number.EPSILON) return 0
        
    const magnitude = Math.floor(Math.max(0, Math.log(discount) / Math.log(10)))
    const epsilon = Math.pow(10, magnitude - 12) // treat last 3-4 significant digits as error
    return Math.abs(Math.ceil(discount - epsilon)) // Math.abs to prevent -0
} 

Test cases:

describe('roundupDiscount', () => {
    it('rounds the item discount correctly for numbers of differing magnitude', () => {
        let epsilon = Number.EPSILON; // machine epsilon - smallest positive number which, added to 1, will produce a value different from 1

        expect(roundupDiscount(1 + epsilon)).toBe(1)
        expect(roundupDiscount(1 + (10 * epsilon))).toBe(1)
        expect(roundupDiscount(1 + (100 * epsilon))).toBe(1)
        expect(roundupDiscount(1 + (1000 * epsilon))).toBe(1)
        expect(roundupDiscount(1 + (10000 * epsilon))).toBe(2) // "error" no longer small

        // test it handles large numbers ...
        const largeNum = 1000000000;
        const largeEpsilon = largeNum * epsilon;
        expect(roundupDiscount(largeNum + largeEpsilon)).toBe(largeNum)
        expect(roundupDiscount(largeNum + (10 * largeEpsilon))).toBe(largeNum)
        expect(roundupDiscount(largeNum + (100 * largeEpsilon))).toBe(largeNum)
        expect(roundupDiscount(largeNum + (1000 * largeEpsilon))).toBe(largeNum)
        expect(roundupDiscount(largeNum + (10000 * largeEpsilon))).toBe(largeNum + 1)

        // test it handles small numbers ...
        expect(roundupDiscount(epsilon)).toBe(0)
        expect(roundupDiscount(10 * epsilon)).toBe(0)
        expect(roundupDiscount(100 * epsilon)).toBe(0)
        expect(roundupDiscount(1000 * epsilon)).toBe(0)
        expect(roundupDiscount(10000 * epsilon)).toBe(1)
    })
})

Answer 2

I'd like roundupDiscount(Number.EPSILON) to be 0

The below code is dodgy. Math.log() finds the logarithm, base e and is never exactly correct except for Math.log(1).

const magnitude = Math.floor(Math.max(0, Math.log(discount) / Math.log(10)))

Better to start with Math.log10 which is far more likely to provide the desired result for discount == powers-of-10.

Math.floor(Math.max(0, Math.log10(discount)))

Still I find this approach weak.

---

Code is really trying to perform a ceiling() on values unless they are only a "little above" an integer value to compensate for computational errors. That "little above" being controlled by - 12 to form 10^-12 or some similar value.

Now code introduces more errors in determining magnitude that get amplified with floor().

IMO, to truly handle edge cases well, use your functions that are designed to convert the binary nature of floating point value to decimal text.

I, not being node.js savvy, take this code idea as a guide.

.toLocaleString() to form the string of the rounded value to as many digits you like.

Then parseFloat() to form the floating point value.

I'd expect this to be slow, but that is a the cost of business.

---

Even if this approach is too slow, it does serves as reference code to compare the proper functionality of alternate code.

---

Personally, I'd try to scale value down a "little bit" and then apply the ceiling.
(Adding 0.0 should prevent any -0.0 sum.)

Math.ceil(discount * (1 - 1.1E-12)) + 0.0
//                             ^^ or 11, 13, ...