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."
1.44th post!
Round down and put the extra aside. Say, in your own account. Like the have-a-penny-need-a-penny jar at the local Gulp-n-Blow.
especially if you *think* you know what your programs are doing.
Pfft... I've been writing programs and working with computers for over 25 years. I *STILL* haven't figured out what they are doing. Come to think of it, I could say the samething about my wife.
If "disco" means "I learn" in Latin, does "discothèque" mean "I learn technology"?
my favorite rounding algorithm is pi(r)^2.
The theory of relativity doesn't work right in Arkansas.
- Mountain Dew
- Couch
- Lack of willpower
- Utter disdain for annual resolutions I made less than a week ago
- DiGiorno's pizzas.
Seems to work.I don't think I know what my programs are doing all the time... :)
I just hope they play nice when I'm not watching.
...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.
[Fuck Beta]
o0t!
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.
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.
Almost correct, but I think it can be simplified to the following:
quidquid latine dictum sit altum videtur.
And the IEEE standard for rounding is Banker's Rounding, or Even Rounding, plus whatever other names it goes by. When rounding to the nearest whole number, when the value is exactly halfway between, i.e. 2.5, the rounding algorithm chooses the nearest even number. This allows the distribution of rounding to happen in a more even distributed manner. Always rounding up, which is what US kids are taught in school, will eventually create a bias and throw the aggregates off.
2.5 = 2
3.5 = 4
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.
So it turns out instead of 2, there are more like 9 different types of people.
The classics:
Those who round a glass of water up (Has been filled)
Those who round it down (Has been emptied)
The oddballs:
The round-half-up crowd(Half or greater is filled)
The round-half-down crowd(Half or less is empty)
The round toward zero types(Always empty)
The round away from zero groupies(Always Full)
The round alternate weirdos(They get interesting when you give them two glasses)
The round random subset(Carry around a coin or die to decide such problems)
And finally...
The truncate ones who cannot handle such a problem and smash the glass to make sure it is empty.
If this signature is witty enough, maybe somebody will like 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.
-5.8 --> -5.8+0.5 --> -5.3 --> truncate(-5.3) = -5.0
which is not what you want.
In c++, using std::floor will give the correct results with this method though
-5.8 --> -5.8+0.5 --> -5.3 --> floor(-5.3) = -6.0 (correct)
whereas :
-5.3 --> -5.3+0.5 --> -4.8 --> floor(-4.8) = -5.0 (correct)
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.
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.
I would say that $3.00 is just as precise as $3.21. If you want less precision, you have to go to $3...
Repton.
They say that only an experienced wizard can do the tengu shuffle.
For pretty much all other cases it is broken, wrong, bad, very bad, and misguided. It is a kludge cut from the same cloth as using red and black ink, parenthesis, or location on the page (and all the permutations thereof) to indicate the sign of a number. Do not try to do any sort of scientific calculations, or engineering, or anything else that matters and round in this way.
Why? Because contrary to what some people think, there is no systematic bias in always rounding up. There are exactly as many values that will be rounded down as will be rounded up if you always round exact halves up. I think the trap that people fall into is forgetting that x.000... rounds down (they think of it as somehow "not rounding").
--MarkusQ
This stuff is still important. Yes the big computers we have on our desks can do high precision floating point. but there are still some very small 4-bit and 8-bit micro controllers that controll battery chargers, control motors that move antenna on spacecraft and the control fins on air to air missles. And then there are those low-end DSP chips inside TV sets and digital cameras and camcorders.... These controllers need to do complex math using short integers and how round off errors accumulate still does matter. Remember: Not all software runs on PCs in fact _most_ software does not.
They left off one that I've used a few times when dealing with graphics, which using their naming convention would be something like "Round Toward Mean". You basically take the mean of the surrounding values in an array or matrix and then round up if the value is below the mean, and round down if it's above the mean.
It's useful for smoothing out images if you use this for each color channel (RGB, CMYK, HSV, etc.).
Famous Last Words: "hmm...wikipedia says it's edible"
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!)