All posts by top-quark

I'm a software engineer of distressingly long standing working for a major international software company. Since their views aren't mine and vice versa, I won't say who.

Rounding Numbers: How Hard Can It Be?

Rules for rounding half up
Credit: tes.com

How hard? Hard enough, apparently, that your computer gets it badly wrong. Tell me, computer, what is 1.015 rounded to two decimal places?

If you see “1.01”, you are using a standards-compliant browser. An eleven year old child knows that “1.01” is wrong and when a kid can see that something’s wrong, it’s just not good enough! So how hard can it be when you put your mind to it? Let’s see.

Algorithms

Before implementing a precise rounding algorithm, we need to figure out what we mean by rounding. For most cases, it’s simple: you just round towards the nearest digit. The tricky case is what to do with those pesky halves. Turns out there’s more than one way to handle them.

Round half towards positive infinity

This is the method we learn at school: 1.5 rounds up to 2. But what do we do about negative numbers? If we apply the round-half-up rule consistently we have to round them up too so that -1.5 rounds up to -1.

Round half away from zero

This is what we get if we apply the round-half-up rule symmetrically: positive numbers are rounded up to become more positive, while negative numbers are rounded down and become more negative.

Round half to even

The problem with the round-half-up algorithms is that they introduce a bias. What this means is that if you round a set of random numbers and take the average, it will not be the same as the average of the originals. This matters a lot in some applications: if you’re a major bank those half pennies mount up! The solution to this bias is to round down as often as you round up. In the case of round half towards even (aka banker’s rounding), halves are rounded to the nearest even digit so that 1.5 and 2.5 both round to 2 while 0.5 and -0.5 both round to 0.

Other algorithms

There are other algorithms which are (almost) never used. Round-half-down or round half to zero simply makes your results look consistently wrong. Round half to odd has the disadvantage that it doesn’t round to 0. Alternate rounding requires that we keep track of the last direction while stochastic rounding (randomly up or down) requires a reliable source of randomness which as any fule kno is hard!

Internet Explorer

If you see “1.02” above, you are probably using Internet Explorer. Presumably, some Microsoft engineer looked at the output from the specification and thought “that’s not good enough” as well.

Implementation

When reading the code snippets in this section, assume the following module wrapper:

(function(window) {
    "use strict";
    ...
})(this);

Which algorithm to use? We’ll give the programmer a choice:

var _ralgs = {
    HALF_UP : 0,
    AWAY_FROM_0 : 1,
    TO_EVEN : 2
};

We can note that a naive implementation – scale up, round, scale back down – isn’t going to cut the mustard. The reason for this is the finite precision of your computer hardware. Tell me, computer, what do you get when you multiply 1.015 by 100?

We can also note that rounding to n decimal places is not an arithmetic operation, it is a presentation operation. Therefore, our rounding algorithm is going to work on the string representation of the number, a bit like humans do. Like all Objects, numbers in JavaScript have a toString operation. The only question is, is it fit for purpose? Tell me, computer, what is the stringified form of 0.0000001?

Tarnation! Admittedly, I don’t have to work with very small numbers very often, but an algorithm that didn’t work in the general case would bother the heck out of me! Looks as though we’re going to have to start by implementing toString ourselves and before we can do that we have to write a function that will zero-pad a string. This really should be a standard method on String, but it’s not hard to do:

// Padding function
var _pad = function(s, padTo, padWith, right) {
    s = s + '';
    var pad = "",
        toPad = Math.max(padTo, s.length) - s.length;
    while (toPad) {
        if (toPad & 1) {
            pad += padWith;
        }
        toPad >>>= 1;
        if (toPad) {
            padWith += padWith;
        }
    }
    return right ? s + pad : pad + s;
};

Don’t be too alarmed reading that while loop. String concatenation is relatively expensive (because strings are immutable) so adding one character at a time is sub-optimal. Instead of doing n concatenations we do, at most, log2 n. Now we can re-implement toString:

// Stringifies numbers, paying attention to very large and very small quantities
var _toString = function(n) {
    var parts = n.toExponential().split("e"),
        mag = parseInt(parts[1], 10),
        _n = parts[0];
    parts = _n.split("."),
    var iPart = parts[0],
        dPart = parts[1] || "",
        sig, ret;
    if (n < 0) {
        iPart = iPart.substring(1, iPart.length);
        sig = '-';
    }
    if (mag > 0) {
        ret = iPart + dPart;
        if (ret.length < mag + 1) {
            // Pad to the right with zeroes
            ret = _pad(ret, mag + 1, '0', true);
        }
        else {
            // Need to insert the decimal place at the
            // right point
            iPart = ret.substring(0, 1 + mag);
            dPart = ret.substring(1 + mag, ret.length);
            ret = iPart;
            if (dPart) {
                ret += '.' + dPart;
            }
        }
    }
    else if (mag < 0) {
        mag = -mag;
        // 0.0 followed by mag-1 x '0' followed
        // by iPart + dPart
        ret = _pad("0.", mag + 1, '0', true) +
            iPart + dPart;
    }
    else {
        return _n;
    }
    if (sig) {
        ret = sig + ret;
    }
    return ret;
};

toExponential gives us a consistent string representation of the number which we can then split to obtain the signficand and exponent. Then it’s just a matter of zero-padding the significand accordingly and sticking the decimal point in the right place. Taking a minus sign into account when padding is bothersome so we remove it and restore it afterwards.

The next bit we have to implement is the function where we “increment” a string, propagating any carry left:

// The numeric value of the '0' character
var _zero = '0'.charCodeAt(0),
// For suppressing -0
_likeZero = /^0(?:\.0*)?$/,
// Numerically increments a string
_incStr = function(s, pos) {
    if (pos >= 0) {
        var p1 = s.substring(0, pos),
            p2 = s.substring(pos, pos + 1);
        if ('.' === p2.charAt(0)) {
            // Skip past '.'
            return _incStr(p1, pos - 1) + '.';
        }
        var d = s.charCodeAt(pos) - _zero + 1;
        if (d >= 10) {
            d -= 10;
            // Carry 1
            p1 = _incStr(p1, pos - 1);
        }
        p2 = String.fromCharCode(d + _zero);
        return p1 + p2;
    }
    // We've incremented off the left edge of the string
    // so do the final carry
    return '1' + s;
};

That’s the boilerplate done. Now we can implement our rounding functions. All take a number and the number of desired fractional digits as parameters. First up, half-up:

// Implementation of round to plus infinity (exact)
var _round2PlusInfinity = function(n, fd) {
   var s = _toString(Math.abs(n)),
       pos = s.indexOf('.');
   // _toString gives x or x.yyy not .yyy
   if (pos >= 1) {
       var nd = s.length, rpos = pos + fd + 1;
       if (rpos < nd) {
           var d = s.charCodeAt(rpos) - _zero,
               up = d >= 5;
           if (d === 5 && n < 0) {
               up = false;
           }
           if (up) {
               // Round up
               s = _incStr(s.substring(0, rpos),
                   rpos - 1);
           }
           else {
               // Simply truncate
               s = s.substring(0, rpos);
           }
       }
   }
   if (n < 0 && !_likeZero.test(s)) {
       s = '-' + s;
   }
   return s;
};

Here we see what that mystery _likeZero regex was for. For negative numbers, we get rid of a bothersome minus sign by working with the abs value. If a value rounds to 0 and we stick the minus sign back on the front, we’ll end up with “-0” which just looks weird. Round half towards even is similar with a little bit of added complexity in deciding whether we round up or down:

// Implementation of round half to even (exact)
var _roundTowardsEven = function(n, fd) {
    var neg = false;
    if (n < 0) {
        // Round half to even is symmetric
        neg = true;
        n = -n;
    }
    var s = _toString(Math.abs(n));
    var pos = s.indexOf('.');
    if (pos >= 1) {
        var nd = s.length, rpos = pos + fd + 1;
        if (rpos < nd) {
            var d = s.charCodeAt(rpos) - _zero, 
                up = d > 5;
            if (d === 5) {
                // Check the previous digit
                var c, _rp = rpos, _d;
                do {
                    c = s.charAt(--_rp);
                }
                while (c === '.');
                _d = s.charCodeAt(_rp) - _zero + 1;
                // Up if the previous digit will be even
                up = (0 === _d % 2);
            }
            if (up) {
                // Round up
                s = _incStr(s.substring(0, rpos),
                    rpos - 1);
            }
            else {
                // Simply truncate
                s = s.substring(0, rpos);
            }
        }
    }
    if (neg && !_likeZero.test(s)) {
        s = '-' + s;
    }
    return s;
};

Implementation of the final algorithm is a doddle:

// Implementation of round half away from zero
var _roundAwayFromZero = function(n, fd) {
    if (n >= 0) {
        return _round2PlusInfinity(n, fd);
    }
    var ret = _round2PlusInfinity(-n, fd);
    if (!_likeZero.test(ret)) {
        ret = '-' + ret;
    }
    return ret;
};

Now we can join them together:

// Rounding function with algorithm specified
var _round = function(n, fd, alg) {
    fd >>>= 0;
    switch (alg) {
        case _ralgs.HALF_UP:
            return _round2PlusInfinity(n, fd);

        case _ralgs.AWAY_FROM_0:
            return _roundAwayFromZero(n, fd);

        default:
            return _roundTowardsEven(n, fd);
    }
};

There’s one last bit of boilerplate before implementing our public API. One thing I dislike about toFixed is that you get trailing zeroes in your output whether you want them or not. You asked for six decimal places in your output? Here you go! Our API will, by default, suppress useless zeroes but the caller can specify a minimum number as an optional argument. We need a function to make that possible:

// Applies minimum / maximum fractional digits
var _trimFraction = function(s, minFd, maxFd) {
    var splitPoint = s.indexOf('.'), i = s, j, f = "";
    if (splitPoint === -1 && minFd === 0) {
        return s;
    }
    if (null == minFd) {
        minFd = 0;
    }
    if (null == maxFd) {
        maxFd = 2;
    }
    if (splitPoint >= 0) {
        f = s.substring(splitPoint + 1, s.length);
        i = s.substring(0, splitPoint);
    }
    if (minFd) {
        // Add trailing zeroes
        for (j = f.length; j < minFd; j++) {
            f += '0';
        }
    }
    else {
        // Trim excess seroes
        f = f.substring(
            minFd, maxFd).replace(/0+$/, "");
    }
    if (f) {
        return i + '.' + f;
    }
    return i;
};

Our public API consists of some properties and a method added to Number.prototype:

// Algorithm specification
window.Rounding = {
    HALF_TO_PLUS_INFINITY : _ralgs.HALF_UP,
    HALF_AWAY_FROM_ZERO : _ralgs.AWAY_FROM_0,
    HALF_TO_EVEN : _ralgs.TO_EVEN,
    // Default rounding method is
    // ROUND_HALF_TO_EVEN
    algorithm : _ralgs.TO_EVEN
};

// Add a roundTo method to Number
var rt = function(maxFd, minFd) {
    if (!isFinite(this)) {
        return this + '';
    }
    // Require numbers >= 0
    maxFd = Number(maxFd);
    minFd = Number(minFd);
    if (!(isFinite(maxFd) && maxFd >= 0)) {
        maxFd = 0;
    }
    if (!(isFinite(minFd) && minFd >= 0)) {
        minFd = 0;
    }
    if (minFd > maxFd) {
        minFd = maxFd;
    }

    return _trimFraction(
        _round(this, maxFd, window.Rounding.algorithm), minFd, maxFd);
}, mName = "roundTo", obj = window.Number.prototype;
if (!(mName in obj)) {
    try {
        Object.defineProperty(obj, mName, {
             value : rt,
             enumerable : false
        });
    }
    catch(e) {
        // Do it the old fashioned way
        obj[mName] = rt;
    }
}

Because of the way we’ve implemented our rounding function, we don’t have to worry that someone might set Rounding.algorithm to “Dave”; this means that we don’t have to use a getter / setter for the property. Some Internet experts expend a lot of hot air on the evils of extending built-in types, but Number is absolutely the right place to add our method since we can now use it in place of toFixed and the ability to extend Objects is a central feature of JavaScript anyway. Do note, however, how we go about adding our method – this is the nice way to do it; stomping over someone else’s roundTo method is not polite!

Let’s try it out. Tell me, computer, what is the result of rounding 1.015 to two decimal places?

Hurrah! Remember that it’s generic enough to handle very small numbers? Tell me, computer, what is 1.25×10-26 to 27 decimal places?

Note, this is not wrong – it is the round half to even algorithm. If we set the algorithm to round half to plus infinity and ask again, we get a slightly different answer:

If you don’t want to use a different rounding function, there’s no reason why we can’t simply fix toFixed! Here’s a patch:

(function() {
    if ((0.1).toFixed(20) ===
        "0.10000000000000000000") {
        // Not broken
        return;
    }
    var m = function(fd) {
        return this.roundTo(fd, fd);
    }, obj = Number.prototype, mName = "toFixed";
    try {
        Object.defineProperty(obj, mName, {
            enumerable : false,
            value : m
        });
    }
    catch(e) {
        obj[mName] = m;
    }
})();

And the answer to the original question of how hard can it be? The answer is: harder than you think!

You can download the complete library or, if you prefer, a a minified version.