Slashdot Mirror
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."
...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.
Helping with organizational effectiveness is our job.
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 can save you the trouble of performing error analysis. An article in the Journal of the ACM provides the details for implementing this feature.
Is it really an "urban legend"? As much of a trope it has become in movies with technological whizzes, Snopes says it was reported in Whiteside's Computer Capers: Tales of Electronic Thievery, Embezzlement, and Fraud , which should have the necessary citation on the case.
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.
You could've hired me.
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.
Some drink at the fountain of knowledge. Others just gargle.
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.