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."
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"?
Almost correct, but I think it can be simplified to the following:
quidquid latine dictum sit altum videtur.
-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)
It sounds like you are saying, instead of rounding to the nearest unit, round to the nearest half unit. If you had read the article you would know that there is no theoretical difference what place value you decide to round to.
You think you can just eliminate the 1/2 bias like that? Ok, now you know what to do with the number 3.5. Now what do you round 3.75 and 3.25 to? You are just shifting the rounding down one binary digit.
You say to not round until the end? You miss the point of rounding, which is necessary due to efficiency, memory, or hardware concerns. Nobody makes 10000 bit ADCs, and even if they did, you'd still need to round the 10001st bit.
I was expecting something a little better than this, like maybe some fast code to study and use.
In Soviet America the banks rob you!
</silly>
Actually, that seems like an interesting concept. I always felt that my computer science class needed to be more challenging, and now I know how to do it!
Why is it that when you believe something it's an opinion, but when I believe something it's a manifesto?
I already got into these types of rounding a decade ago. For a really good read on an FPU implementation, try to find a copy of the Motorola 68881/2 Programmer's Reference Manual.
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.
I think you might be mistaken. Round to the nearest even is statisticly significantly more accurate. Rounding halves up does nothing for accuracy as you seem to imply. Large data sets of any type of data will be biased if rounding halves up, whereas rounding to the nearest even is ever more accurate with each datapoint. Your statement about rounding to even being bad makes me think you haven't fully grasped the underlying concept, I've never seen rounding halves up used for anything in a major environment simply because it is almost always the wrong thing to use.
Regards,
Steve
For illustration, suppose we use a floating-point format with a 10-bit mantissa. For a fixed exponent (say 0), this can represent values from 1.0 to 1 1023/1024, in 1/1024 increments. The AVERAGE of these UNROUNDED values is 1 1023/2048, which is LESS THAN 1.5. However, if all these values are rounded (with 0.5 rounding up), the AVERAGE of the ROUNDED values will be EQUAL TO 1.5, an average increase of 1/2048. Thus, this type of rounding introduces a measurable positive bias into the arithmetic.
No, the "bias" came from your choice of data (and your unrealistic expectation that the average of a set of rounded values would equal the average of the unrounded set).
Such examples are as easy to construct as they are misleading. Suppose we instead take the values {0.2, 0.3, and 0.5}. Their average is 1/3, and if we round them ".5 up" we wind up with {0,0,1} with exactly the same average. On the other hand, if we round them with ".5 to even" we wind up with {0,0,0} with the average of zero and an "error" (by your metric) of 100%.
--MarkusQ
For example, the number 4.56106531 would be rounded to 4 in the "nearest even" case or to 5 in the "round up" case But clearly, the "nearest even" result is less accurate, and introduces a significant bias. 4.56106531 is closer to 5 than to 4, and should be rounded up. Always.
This is the wrong rule. The number 4.56106531 would be rounded to 5 with both techniques. The "nearest even" technique for rounding to the nearest integer only applies to 4.50000000. In this case, you would round the number to 4. You might say what's the point, since this is a very unlikely case. However, if you only have two digits to work with it becomes much more significant.
At this point, you may object that you aren't planning on truncating before you apply the rule (or, equivalently, you only do the even odd dance on "exact" halves). But how did you get an "exact" half? Unless you have infinite precision floating point hardware, less significant bits fell off the bottom of your number; unless they were all zero your "exact half" is the result of truncation and the above logic still applies.
The "exact half", for all you know might be below .5 or might be
above .5. You seem to be assuming it is the result of truncating a
single number. The rounding occurs during arithmetic operations and,
for all you know, the real extra is just as likely to be below .5 as
it is above .5. That's the essence of rounding and why we don't use
truncation.
But just for fun, lets take the case where you are inputing the number into the computer. If the number has a number of significant digits more than the machine then for most problems the number is just as likely to be a little below the given number as it is above, therefore you should use "nearest even" to remove bias. If the number has a number of significant digits less than or equal to the machine, you just enter the number.
As an rough argument why "nearest even" works, every time you do an arithmetic operation with rounded numbers the new number is just as likely to be a little too big as it is to be a little too small. (This is why we represent rounded number as x*(1 + or - epsilon).) Therefore rounding 1.0 to 1 is ideal since the number is just a likely to be a little smaller as it is to being a little bigger. Rounding 1.1 to 1 starts introducing bias since you are shrinking the number. However, the bias for 1.1 balances out the bias for 1.9, and the bias for 1.2 balances out the bias for 1.8. However, if you continue, the bias for 1.5 is not balanced out and the sum of numbers tends to grow. One way around this is to flip a coin for 1.5 and round up half the time and down the other half. This is expensive, so a cheap alternative is to just use the next digit as the random coin; round up if it's odd and round down if it's even..
Last, as an appeal to experts, Reiser and Knuth [1975] disagree with you. In fact, Knuth has a write up in one of his Art of Programming books on the issue. A short but online explanation can be found here in the section Exactly Rounded Operations.
Chris Mesterharm
Absolutely false. Let me explain that in simpler terms: wrong, wrong, wrong, wrong wrong.
A good package will help a programmer avoid the worst problems in the simplest situations.
The worst situations are not solvable even by human experts backed by state of the art theory.
The bottom line is that numerical analysis is a very deep speciality, roughly like compiler design is a very deep specialty. In neither area is there some package that will solve your problems for you.
Standard math libraries that implement functions like square root, exp, ln, etc, long ago were implemented by people like you, who didn't know nor care that those functions might be somewhat inaccurate.
Math libraries for standard languages, for the last 20 years or so, have instead been designed and implemented by specialists who guarantee that the last bit of every result is as accurate as possible -- whereas some non-specialist like you might merely be able to guarantee that each function kind of sort of yields almost the right result, as long as "right" means maybe 16 bits of accuracy.
Numerical analysis is a deep subject. If you aren't a specialist in the subject, you may as well shut up about it, because everything you say will be wrong, and you will spread misinformation.
In particular, you cite an interval arithmetic package. Such things are certainly very important in numerical analysis.
But the notion that such things completely solve all numerical analysis programs is completely laughable. Take a course in a subject before you conclude that a subject has been solved!!!
Professional Wild-Eyed Visionary