## Rounding Algorithms 279

Posted
by
CmdrTaco

from the now-that's-just-wierd dept.

from the now-that's-just-wierd dept.

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."*
## Round this! (Score:5, Funny)

## Re:Round this! (Score:3, Funny)

## Re:Round this! (Score:3, Interesting)

## Most important... (Score:5, Funny)

## Re:Most important... (Score:2)

## Re:Most important... (Score:5, Informative)

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

## Re:Most important... (Score:2, Informative)

## Re:Most important... (Score:4, Informative)

## Re:Most important... (Score:4, Interesting)

## Re:Most important... (Score:5, Interesting)

Computer Capers: Tales of Electronic Thievery, Embezzlement, and Fraud [amazon.com], which should have the necessary citation on the case.## Re:Most important... (Score:2)

## Re:Most important... (Score:2, Funny)

Gulp-n-Blow.There has to be a joke here, I know there does.

## Re:Most important... (Score:2)

## Think you know.... (Score:5, Insightful)

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.

## Re:Think you know.... (Score:2)

Come to think of it, I could say the samething about my wife.If your wife is getting rounded, I'd say she's either pregnant or bulimic. Either way, you have a problem.

## Re:Think you know.... (Score:5, Funny)

Why would my wife being pregnant be a problem?You'll know 13 years from now

## Re:Think you know.... (Score:3, Funny)

## Re:Think you know.... (Score:2)

## Slide Rules and precision (Score:5, Interesting)

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:Slide Rules and precision (Score:3, Interesting)

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

## Re:Think you know.... (Score:2)

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 you've been trying to program your wife for 25 years, I think I may see your problem...

## my favorite rounding algorithm (Score:5, Funny)

## My personal rounding program (Score:5, Funny)

## Re:My personal rounding program (Score:4, Funny)

* DiGiorno's pizzas.

Seems to work.

So that's rounding towards positive infinity, right?

## Ugh (Score:3, Funny)

all the time...I just hope they play nice when I'm not watching.

## I read the first half of the article... (Score:5, Interesting)

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

## Re:I read the first half of the article... (Score:2, Informative)

## Re:I read the first half of the article... (Score:3, Informative)

## Re:I read the first half of the article... (Score:3, Informative)

This is a great reference article! If you are programmer working with numerical algorithms, keep this article handy.This one too: What Every Computer Scientist Should Know About Floating-Point Arithmetic [sun.com].

## What about... (Score:3)

## Re:What about... (Score:2)

## Computer games should use floor(x+rand()) (Score:2, Troll)

This means that every little bonus that the player gets might have an impact on the integer result. Example: phaos.

The "other" neat thing is that the expected value of

floor(x+rand()) == x

with 0.0=0.0

## Office Space (Score:5, Funny)

## Re:Office Space (Score:2)

## Re:Office Space (Score:2)

Supes 2 was the one with the three Krypton criminals introduced at the beginning of Superman I then leftSupposedly the original story was both movies, but they editied for time.

3 was with Richard Pryor and the red kryptonite and the self-learning computer and red kryptonite that causes Superman to act evil, and was pretty mediocre.In a just world they'd have a Director's Cut with Richard Pryor actually doing his act. Rated R for Language, naturally.

## Re:Office Space (Score:2)

MICHAEL: It's pretty brilliant. What it does is where there's a bank

transaction, and the interests are computed in the thousands a day in

fractions of a cent, which it usually rounds off. What this does is it

takes those remainders and puts it into your account.

PETER: This sounds familiar.

MICHAEL: Yeah. They did this in Superman III.

PETER: Yeah. What a good movie.

## Don't round much myself (Score:2)

I mostly program using fixed integer arithmetic, so I don't do much

plainrounding. But I do frequently need to do division with rounding up to nearest integer value. For that I use:## floating point (Score:3, Interesting)

## The canonical reference... (Score:2)

## Re:The canonical reference... (Score:2)

*grin*

<fry>I get it!</fry>

## Interval arithmetic (Score:5, Interesting)

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 performingerror analysis. An article [acm.org] in the Journal of the ACM provides the details for implementing this feature.## Re:Interval arithmetic (Score:3, Insightful)

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

## IEEE Standard (Score:4, Informative)

2.5 = 2

3.5 = 4

## Re:IEEE Standard (Score:2)

And the IEEE standard for rounding is Banker's RoundingThat's what I have always used for programs that calculate a cost from some other factors; for instance labor costs are sometimes calculated by multiplying minutes by some factor. The result is often a decimal value that needs to be rounded to dollars and cents. If you use banker's rounding, and you should, then the bean counter upstairs will probably get the same result as your program does. This is a good thing.

## Re:IEEE Standard (Score:2)

## Only with money in fractions (Score:5, Informative)

alreadybiased 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 nottry 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 (Score:2, Insightful)

## Re:Only with money in fractions (Score:4, Informative)

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:

lessaccurate.more accurate.rounding to the nearest even, whereasrounding halves upis 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).

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

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

allzero 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

## Re:Only with money in fractions (Score:3, Insightful)

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

## Re:Only with money in fractions (Score:3, Informative)

## Re:Only with money in fractions (Score:2)

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").This is incorrect.

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

## Re:Only with money in fractions (Score:5, Insightful)

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

## Re:Only with money in fractions (Score:3, Informative)

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## Stifling innovation in rounding (Score:2)

## Social Applications (Score:5, Funny)

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.

## Rounding Algorithms are... (Score:2)

compileris doing. My beautiful code goes into one end and comes out as an executable file that segfaults. Of course, some twit always say the problem is with my beautiful code and not the stupid compiler.## Re:Rounding Algorithms are... (Score:2)

## How many times do I have to explain this (Score:2, Insightful)

</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!

## In-Story Dupe? (Score:2)

## Re:In-Story Dupe? (Score:2)

If I floor a number, always rounding down. If I ceiling the number, always rounding up, positive or negative.

trunc(-1.5) = -1 = round2zero(-1.5)

trunc(1.5) = 1 = round2zero(1.5)

floor(-1.5) = -2 = rounddown(-1.5)

floor(1.5) = 1 = rounddown(1.5)

ceiling(-1.5) = -1 = roundup(-1.5)

ceiling(1.5) = 2 = roundup(1.5)

## so, what's the diffrence (Score:2)

## I was expecting something more detailed than this (Score:3, Insightful)

## Precision (Score:4, Informative)

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

## Re:Precision (Score:2)

I would say that $3.00 is just as precise as $3.21. If you want less precision, you have to go to $3...Me too, but I always got those marked wrong in Science class - purposely because nobody could explain to me why 3.00 was less precise than 3.21, but according to the textbooks it is. I don't get it.

## Re:Precision (Score:3, Informative)

## All I ever needed to know about rounding, I... (Score:2)

Out on the streets, that's where we'll meet

You make the night, I always cross the line

Tightened our belts, abuse ourselves

Get in our way, we'll put you on your shelf

Another day, some other way

We're gonna go, but then we'll see you again

I've had enough, we've had enough

Cold in vain, she said

(Pre-chorus)

I knew right from the beginning

That you would end up winnin'

I knew right from the start

You'd put an arrow through my heart

(Chorus)

Round and round

With love we'll find a way just give it time

Ro

## He missed some (Score:3, Interesting)

combinatorial compression(enumerative coding).## Old school (Score:2, Insightful)

## This stuff is still matters (Score:4, Insightful)

## At least (Score:2)

## Round Toward Mean? (Score:4, Informative)

It's useful for smoothing out images if you use this for each color channel (RGB, CMYK, HSV, etc.).

## I never thought I knew what was happening... (Score:3, Interesting)

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

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

perceivedrange (+/- 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...

## That is nothing... (Score:3, Interesting)

## Re:RIAA Rounding (Score:4, Insightful)

Almost correct, but I think it can be simplified to the following:

## Re:RIAA Rounding (Score:2)

## Re:RIAA Rounding (Score:2)

## Re:Applications (Score:3, Interesting)

## Re:Seems dumb to me (Score:2)

In Casinos, when "counting" a change in a machine, they use rounding.

The wieght the money (not count it).

Multiple with the exchange factor (100lb = $133.34 in Pennies).

Round the amount with allernating Round-Up / Round-Down on seccuessive wieghings for the machine.

This way over time the rounding error will tend to average to 0.

## Re:Seems dumb to me (Score:2)

## Re:Seems dumb to me (Score:3, Funny)

## Re:Seems dumb to me (Score:2, Informative)

As the article infers, time contraints on a system will often mean that you can't "afford" to do math as precisely as your architecture might theoretically allow you to. This is a common hurdle to overcome when you're working on embedded real-time systems: ie. the need to find a compromise between speed and accuracy. Just because you

cando an operation on two floats in a loop 1000 times doesn't mea## Re:Seems dumb to me (Score:2)

Yes, for certain types of numerical problems, there is a bounded precision, or set of values, for which you could create a specialized counting system (ie. many financial pr

## Re:Seems dumb to me (Score:2)

Windows Calculator, for example.

## you seem to be missing the point (Score:3, Insightful)

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 neces

## Re:Seems dumb to me (Score:4, Interesting)

## Re:Accounting Software (Score:5, Interesting)

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.

## Re:Accounting Software (Score:2)

## Re:Accounting Software (Score:3, Interesting)

## Re:Accounting Software (Score:2)

## Re:Don't you just... (Score:2, Offtopic)

## Re:Canadian, eh? (Score:2)

## Re:Don't you just... (Score:2)

## that's rounding up (Score:2)

## Re:that's rounding up (Score:2)

## Re:that's rounding up (Score:3, Interesting)

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

## Doesn't work for negative numbers. (Score:4, Insightful)

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)

## Re:Doesn't work for negative numbers. (Score:2)

## Re:Add and truncate (Score:5, Interesting)

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.

## Re:the best rounding algorithm (Score:2)

is the one used by richard pryor's character in superman iii to steal all of the half pennies from his company's payroll and become fabulously richNah, I think these guys [imdb.com] did it better...

## Re:Round Random? Why? (Score:2)