Rounding Algorithms

dtmos writes "Clive Maxfield has an interesting article up on PL DesignLine cataloging most (all?) of the known rounding algorithms used in computer math. As he states, "...the mind soon boggles at the variety and intricacies of the rounding algorithms that may be used for different applications ... round-up, round-down, round-toward-nearest, arithmetic rounding, round-half-up, round-half-down, round-half-even, round-half-odd, round-toward-zero, round-away-from-zero, round-ceiling, round-floor, truncation (chopping), round-alternate, and round-random (stochastic rounding), to name but a few." It's a good read, especially if you *think* you know what your programs are doing."

I read the first half of the article...

[under_score]

...where it discusses the various rounding methods. I had actually thought of/used most of them. The one that was new to me was the round-half-even (banker's rounding). Very cool idea, and I had no idea it was commonly used.

This is a great reference article! If you are programmer working with numerical algorithms, keep this article handy.

Re:Most important...

[PapayaSF]

Round down and put the extra aside. Say, in your own account.

It's a classic computer crime/urban legend [snopes.com], and has been used in various films.

floating point

[BigMFC]

I'm currently working with floating point accumulation and I've come to realize that rounding is unbelievably important when it comes to floating point. For long accumulations or a series of operations you need round to nearest functionality, but even this can be insufficient depending on the nature of the numbers your adding. If truncation is used however, although the easiest to implement in hardware, the error can add up so fast that it'll stun you. It's good to see a fairly comprehensive summary of techniques out there that doesn't require wading through the literature.

Interval arithmetic

[Diomidis Spinellis]

Rounding towards the nearest neighbour is the default and ubiquitously used rounding mode. The complementary rounding modes (round toward -+ infinity or 0) are useful for doing calculations with interval arithmetic: a calculation can be performed twice with opposing rounding modes to derive an interval value for the result. If all operations are performed in this way, the final result of a complex calculation is expressed as an interval providing the range in which the real value will be (remember, often floating point numbers only approximate the real number). Using such a package [sun.com] can save you the trouble of performing error analysis. An article [acm.org] in the Journal of the ACM provides the details for implementing this feature.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Applications

[__aaclcg7560]

It's called ShareBuilders [sharebuilders.com]. I got a dividend for a princely sum of $2.20 USD and it was re-invested for free as 0.0385 of one share. Although I wished it would round up my stock shares somtimes. I don't like seeing 27.9995 shares when it really should be 28 shares. I hate being cheated out on 0.0005 of a share. :P

Re:Accounting Software

[renehollan]

GST (a VAT equiv.) in Canada and QST in Quebec round UP. Always.

So, 7% GST on a $1 purchase, yields $1.07. On a $1.01 purchase, yields $1.09 ($1.01 + $0.0707 rounded to $0.08 = $1.09).

It used to be that Quebec added their 8% PST not on the amount excluding GST, but the amount including GST, rounded up of course, and it too was rounded. So $1.01 + 7% GST = $1.09. $1.09 + 8% PST = $1.18. Dunno if they replaced that with the 15% "harmonized" sales tax (paid to the Feds and then partially reimbursed to the province to be equivalent to the combination of 7% GST and average provincial 8% PST -- apparently Quebec was the only province to calculate their PST on top of the GST), but I doubt it.

Slide Rules and precision

[goombah99]

These days kids are not taught to round. Instead you just do the compuations at absurdly large precision then on the last step round off. This way you don't accumulate systematic round-off error. It's good as long as you have the luxury of doing that. It used to be that C-programmers had a cavalier attitude of always writing the double-precision libraries first. Which is why Scientific programmers were initially slow to migrate from fortran.

These days it's not so true any more. First there's lots of good scientific C programmers now so the problem of parcimonius computation is well appreciated. Moreover the creation of math co-processing, vector calcualtions, and math co-processors often makes it counter-intuitive what to do.

  For example it's quite likely that brute forcing a stiff calculation is double precision using a numeric co-processor will beat doing it in single precision with a few extra steps added to keep the precision in range. So being clever is not always helpful. people used to create math libraries that even cheated on using the full precision of the avialable floating point word size (sub-single precision accuracy) since it was fast (e.g. the radius libs for macintoshes) Pipelining adds more confusion, since the processor can be doing other stuff during those wait states for the higher precision. Vector code reverse this: if you are clever maybe shaving precision willlet you double the number of simultanoeus calcualtions.

In any case, what was once intuitive: minimal precision and clever rounding to avoid systematic errors means faster computation is no longer true.

Of course in the old days people learned to round early in life: no one wanted to use a 5 digit precision slide rule if you could use a 2 digit precision slide rule.

Re:Seems dumb to me

[Jekler]

Excellent example. I've noticed in writing game systems, there's numerous situations in which rounding to the nearest is just plain wrong. Physical simulations are one area that, even in a game, is a critical issue. Round the wrong way and every object in the world behaves like it has an invisible force field around it. Another situation is that in successive bounds checking, if you we continually round in the same direction (e.g. based on a previously determined value), you end up with a bounding box that grows over time. In a real time game with values being calculated 60+ times per second, within an hour characters can't get closer than 10 feet to an object.

Re:Add and truncate

[Lord Crc]

When I need to implement rounding, I add .5 and then truncate. I believe (perhaps naively) that this is efficient because of the lack of branching.

Where I'm comming from, the FPU is by default set to perform rounding, so to truncate, the FPU control word has to be modified, the move performed, and then the control word has to be restored. This makes truncating a LOT slower than rounding.

He missed some

[Nightlight3]

There is also a delayed rounding [arxiv.org] (see page 7-8) used in combinatorial compression (enumerative coding).

Re:Accounting Software

[TapeCutter]

I worked at a large telco when Australia introduced 10% GST to replace a dizzying array of existing sales taxes and rules. I was assigned to represent the interests of our system in the company wide discussions that went on for a long time about how to handle GST rounding errors. Eventually something like this article was produced showing various rounding algorithims and their pros and cons and a mandated algorithm was given to all projects. The extreme amount of time, effort and documentation was (in my mind incorrectly) blamed on the executives ignorance of floating point limitations in computing.

The execs eventually told us they were mainly concerened that any unavoidable error should be in the customers favour...problem solved. Their downfall was not ignorance it was because they ran the meetings poorly, we were simply there to listen and answer questions. ie: They set themselves up to immediately stray out of requirements, the high level problem was forgotten and the meetings became a series of informal discussions on the wonderland of floating point. They completely missed the fact that GST was the same as existing sales taxes except for the "customer's favour and disclosure" mandates, they were way to busy tring to convert X/11 into dollars and cents.

Anecdote time...

[protocoldroid]

I once heard an anecdotal tale... Of an accountant, who had his wife balance the household checkbook (as a favor, so he wouldn't have to do the household paperwork as well as the paperwork from the house). 20 Years after she had been balancing the checkbook... The husband found out that she had been rounding to whole dollar amounts!!!

In a hurried rush, he went through their records, and rebalanced the checkbook... After 20 years of rounding the difference he found: $.07 in their favor :)

Re:Slide Rules and precision

[Detritus]

From what I recall about C on the PDP-11, single precision didn't buy you much extra speed on the FP-11 (hardware floating point unit), so why not use double precision for all floating point operations?

See the PDP-11 Handbook (1979) [bitsavers.org] for instruction timings.

Re:that's rounding up

[Sarisar]

I know you're joking, but where I used to work (a large multinational financial institution, well insurance company) they almost always simply truncated or rounded up to make them end up with more money that way.

One exception was for when people were making payments into a pension scheme because there were exceedingly strict government rules about what to do. Although I forget the details now, but something about putting a percentage of your salary into the pension scheme we couldn't take MORE so we had to truncate then, otherwise if they wanted to put in 2% salary and we took 2.000001% they could sue us over it or something.

I also remember a maths teacher pointing out why interest is paid monthly on what you have in the account at the beginning of the month, otherwise you could make money by taking your money out and putting it back in every day, or hour, or minute if they calculated it that way (just check for yourself it you want!)

I never thought I knew what was happening...

[nick_davison]

It's a good read, especially if you *think* you know what your programs are doing.

I gave up assuming I knew exactly what my programs were doing right around the time I gave up writing assembly code. Actually, I gave up a little prior to that when I realised I wasn't very good as assembly code but that kind of clouds the point.

For any given high level language, the moment concepts start getting abstracted out, all kinds of false assumptions start getting made based on those assumptions.

Here's one:

Try

public class massiveadd {

        public static void main(String[] args) {
                double a=0.001;
                double b=0;
                for (int i=0; i<1000; i++) {
                        b+=a;
                }
                System.out.println(b);
        }
}

..or the equivalent in your language of choice.

Before you run it, what do you figure you'll get? Please tell me you didn't honestly think you'd get 1?

If you can't even rely on floating point numbers being accurate when well within their perceived range (+/- 2^1023 to 2^-52 is not actually the same as every possible number to that degree of accuracy, despite most assumptions) then, odds are, rounding isn't going to matter that much either.

That said, at least 0.5 has the decency to fit really nicely in to binary as 2^-1 and so you can argue, with certainty, that the number you have is 0.5 before getting in to arguments about whether to round such a number up or down.

Here's one for you though...

double a=0.001;
double b=0;
for (int i=0; i

Except what should be 0.5 has now wandered off to 0.5000000000000003 and even if you do try rounding point fives down, it's now greater than 0.5 anyway - so you'll get one instead of zero...

Which raises the argument - just because you happen to be passing 0.5 in to your rounding function and are arguing which way it should go, what on earth makes you think 0.5 is the correct value of whatever you were working with anyway?

The point of all of this being that these things are cool concepts to know to show off at nerd cocktail parties (OK, over a D&D game is more likely) but open a whole can of worms if you actually want to get authoratative on the subject as one assumption getting questioned leads to another and another. For a very few, it's worth discovering all of the many variants - which likely requires an indepth knowledge of how the compiler works and you're back at assembler anyway. For everyone else, beyond the nerd show off, it's about degrees of comfort and, in most cases, that degree is... leave the lid on the can and back away slowly.

And that leaves me where I am. I'm aware that there're concepts like which way rounding goes, what happens with small decimals, etc. and, luckily for me, I'm in a field where thorough testing is considered accurate enough. Actually freaking out about such issues just feels like coder OCD.

Also important in audio

[ockegheim]

DSP was briefly mentioned in TFA. These days, most audio is recorded in 24 bits or more, but needs to be rounded to 16 bits to master on to CD. Simple truncation can cause harmonic sounds at low levels, so a high frequency (generally inaudible) noise is added to the signal. This is called dithering, and can make audible signals that would be truncated to zero. I've heard it happen. Even stranger is that the added noise peaks at 25-30dB louder than sound you can hear.

That is nothing...

[McSnarf]

I remember a project ages ago (before the Pentium rounding bug). The customer (a state railway company) wanted to calculate fare tables. For that, they needed to be able to round up (2.1 -> 3), down (3.9 -> 3) and commercial (2.5 -> 3). Nothing too fancy so far. However, they also needed this operation to be carried out on PARTS of a currency unit - as in $0.20. Rounding up here would mean $3.04 -> $3.20. A typical scenario would look something like this : From 1-20km, the fare is number of kilometers multiplied by .32, rounded up to the next $0.10, then multiplied with a "class factor" of 1 for second and 1.5 for first class. (And so on, and so on...) Calculating a complete fare table at that time would take about 12 hours on a serious size Tandem computer. (And of course, the program was written in a mix of COBOL and FORTRAN...)

Re:Round this!

[igny]

I and my friend once talked about how to own half of a penny. We came to a solution to use randomness, you flip a penny, and depending on the outcome my friend has the penny or I have it. The problem was that uncertainty is removed after the flip, and I either have it or not, and it is not quite the same as owning 1/2 penny. So for a while we flipped the penny every time we discussed the penny to keep the uncertainty.