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."

Comments

Re:Most important...

[slothman32]

There's some straight line algorithm that uses a similar method.
It keeps adding the slope value for every x increment and when it overloads it also makes the y position go up one.
Or something like that. Bresenham's I believe.

To get on topic I would use the usual "(x).5 to (x+1).499~9 goes to (x+1)" way.
For negative, just ignore the sign when doing it, e.g. -1.6 -> -2

IEEE Standard

[Anonymous Coward]

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

Precision

[Repton]

for example, rounding a reasonably precise value like $3.21 to the nearest dollar would result in $3.00, which is a less precise entity.

I would say that $3.00 is just as precise as $3.21. If you want less precision, you have to go to $3...

Only with money in fractions

[MarkusQ]

"Bankers" rounding is only appropriate in a rather restricted range of problems; specifically, where you are more worried about "fairness" than about accuracy, and have a data set that is already biased towards containing exact halves (generally because you've already rounded it previously).

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

Re:Only with money in fractions

[MarkusQ]

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.

On the contrary, I understand and have worked with this sort of thing for years. I know whereof I speak, and the situation is exactly opposite of what you claim. Specifically:

• Round to the nearest even is statistically ssignificantly less accurate.
• Rounding halves up is significantly more accurate.
• Large data sets of almost any type of data will be biased if rounding to the nearest even, whereas rounding halves up is ever more accurate with each data point.

Note that this is basically your list, with the claims reversed. So we disagree totally. Now let me explain why I am correct. First, let's review what you do when you round to the nearest integer (without loss of generality; rounding to the nearest 1/10th, or even 1/137th, is isomorphic).

1. You start with a number which has a (potentially infinite) string of digits to the right of the decimal place
2. You drop (truncate) all but one of the unwanted digits.
3. You conditionally change the lowest order digit you intend to keep
   • For "round up" you add one to it if the remaining unwanted digit is 5,6,7,8, or 9
   • For "round to nearest even" you add one to it if the remaining unwanted digit is 6,7,8, or 9, or if it is odd and the remaining unwanted digit is five.
4. You drop the remaining unwanted digit

Note that the only difference in results between these rules comes from numbers where:

• The last digit to be kept is even and
• The first of the digits to be disposed of is 5

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.

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 only common case where it doesn't apply is (as I stated originally) when dealing with money, where 1) your sample is biased to contain "exact halves" and 2) it is more important to be "fair" than it is to be accurate. This, in any case, is more of a convention than a fact of mathematics; we agree that money is tracted to a certain point and ignore the half pennies owed and the $0.00004537531 of interest due on them; if we didn't even money would not be an exception to the logic above.

-- MarkusQ

Round Toward Mean?

[miyako]

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.).

Re:Most important...

[Mr Z]

That's the basis behind delta-sigma modulation and Floyd-Steinberg dithering. You carry forward the cumulative error from previous quantization, adding it to the current term. Then you quantize as desired. Over multiple samples, the error gets spread out, such that the local average is very close to the original signal.