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 think you mean:
Round-up, Round-down, get around-toward-nearest,
I get around-half-up,
Yeah,
Get around-half-down, round-half-even, round-half-odd, I get around-toward-zerowooooooHHHHooo!
blarg.
"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.""
Hey! Were's ground round on that list?
In fact, why not just do everything in binary? "after all the computer itself does"!
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.
Double it and add Thirty, or is that the metric conversion for Beer?
Fantasy remains a human right; we make in our measure and in our derivative mode... -- JRR Tolkien
RIAA method:
if (sales(type_cd,2005) < sales(type_cd,2004)) {
set_sales(type_cd,2005)=0;
blame_pirates();
}
A feeling of having made the same mistake before: Deja Foobar
...is the round-spam-spam-random-spam-round algorithm.
...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 to the nearest square?
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.
Computer games should round randomly.
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
I'm still trying to figure out what people mean by 'social skills' here.
When you multiply and divide you often end up truncating/rounding whether you intend to or not. You just don't have enough bits for the precision you need. If you have enough operations, you can end up with some significant errors. That's why DSPs have double wide busses internally.
My own problem was creating a bunch of multiple choice student questions and neglecting to account for the truncation that resulted when I displayed the numbers. Needless to say, the students were annoyed when none of the answers were exactly what they calculated.
[Fuck Beta]
o0t!
Far from being merely academic, this could be useful for all the banking accounting programmers out there collecting fractional amounts of money. A third of a cent here, a tenth of a cent there, pretty soon it adds up to real money!
try { do() || do_not(); } catch (JediException err) { yoda(err); }
One of my perennial complaints against accounting software (at least here in Britain) is that they round half pennies differently from the government's rules on Value Added Tax. So someone buying by mail order who sends a cheque for £25 plus 17.5% VAT rounds down (correctly) and the **** accounts program generates an invoice rounding up (incorrectly) and I am for ever writing an invoice with an extra 1p line to correct the error.
I mostly program using fixed integer arithmetic, so I don't do much plain rounding. But I do frequently need to do division with rounding up to nearest integer value. For that I use:
Wanted: witty unique signature. Must be willing to relocate.
Why not just round to the nearest in all cases?
If you're worried about cumulative rounding error buildup, then don't round until after you've accumulated. After all, you're not adding things up with pencil and paper anymore, are you?
If you disagree with me on social issues, then it's pretty clear that you are a narrow-minded bigot.
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.
that's not really inviting people to visit TFA.
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 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.
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 rich
rip dude
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
... nothing in comparison to trying to figure out what the compiler is 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.
What's the difference between round-toward-zero and truncate is? Or floor round and round down? Or ceiling round and round up?
Play Command HQ online
between round to zero and floor, and round to infinity and ceiling?
autopr0n is like, down and stuff.
Discovered the hard way that Fix() in VB doesn't act as I would expect.
Fix((580# * 1.3636)*10000#) gives 7908879 rather than 7908880
This way to the egress...
...for all things floating-point: What Every Computer Sceintist Should Know About Floating-Point Arithmetic. I keep a copy of this handy whenever I have to play with floats and doubles (except for the odd game of Water Tennis, of course).
Just junk food for thought...
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.
...in federal pound-me-in-the-ass prison.
your algorithm always rounts 0.5 up.
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)
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!
...useless. This may be a bit off topic but I was trying out C# the other day and just about all my doubles and/or floats got screwed up. And it wasn't even division or multiplication! It was simple addition and subtraction. I would enter maybe 1 and .6, subtract them, and instead of .4 I'd get... .3999999393993489348938428975932498 or .40000000000000000000000000000000000001
Had to use the decimal datatype for anything wortwhile, meh. Anyone know why my floats and doubles were rendered useless?
Enough said!
Try this. It just might be a lot faster. It copies the sign bit from the value to be rounded to the 0.5, adds 0.5 to positive values or subtracts 0.5 from negative values, then truncates. Of course, I haven't tried it so it just might be slower than a properly inlined and optimized floor() function. But it should be faster if your architecture can move values directly between general and fp regs (unlike SPARC... :-P):
// IEEE sign bit is first // set sign bit for half // add .5 to positive x, subtract .5 from negative x // truncate and return
typedef union masker
{
double d;
int64_t n;
} masker_t;
int round( double x )
{
static const int64_t mask = 1LL 63;
masker_t half;
half.d = 0.5;
masker_t a;
a.d = x;
half.n |= ( a.n & mask );
x += half.d;
return( ( int ) x );
}
Why would you even bother rounding if you didn't know whether the result was going up or down?
No sig for you!
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.
learned from Ratt:
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
Round and round
What comes around goes around
I'll tell you why
Dig
Lookin' at you, lookin' at me
The way you move, you know it's easy to see
The neon light's on me tonight
I've got a way, we're gonna prove it tonight
Like Romeo to Juliet
Time and time, I'm gonna make you mine
I've had enough, we've had enough
It's all the same, she said
(Pre-chorus)
(Chorus)
Yeah!
Solo
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
(Chorus)
Round and round
With love we'll find a way just give it time, time, time, time
Round and round
What comes around goes around
I'll tell you why, why, why, why
Round and round
// TODO: Insert Cool Sig
</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?
There is also a delayed rounding (see page 7-8) used in combinatorial compression (enumerative coding).
I prefer to use blame_ninjas() myself.
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.
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.
At least this Slashdot poster appears to be well-rounded.
Weeks of coding saves hours of planning.
When inlined, that if-statement will prevent efficient loop pipelining. If you're processing a lot of floating-point numbers and performance matters, that won't be very fast.
And the way to truncate floating point numbers in C is to assign them to a integer type.
That's one of the many things about Visual Basic that I always hated. Instead of doing what you expected it to do when casting a floating point number to an integer, the @#$& thing would round up, forcing you to wander through practically worthless help screens to find a simple way to undo what it did. Rounding should be bloody well left to the programmer. If you don't know how to round something, you have no hope getting a simple program to work.
If you, or someone else, might add all the numbers together later on, and you want them to get the right sum. Randomizing is the only way to do this if, for example, you have a list of identical numbers and you don't want to create any simulated 010101010101 pattern by alternating instead of randomizing.
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 am not from Canada, I'm from Southern California.
Fantasy remains a human right; we make in our measure and in our derivative mode... -- JRR Tolkien
When wifey is in with the doctor, the husband will pick up an OB wheel we have in the waiting room. The OB wheel works sort of like a slide rule--you put one notch on when the baby was conceived, and the other notch tells you when the baby is due. Or, put one notch on when you've been told the baby is due, and the other notch will tell you when the baby was conceived. There is an important concept in that last sentence.
Guys will turn the wheel, look perplexed, ask to look at a calendar, look perplexed some more, and then approach a staff member to ask how to use the wheel, thinking they must not be using it right.
This is the point where I go hide.
Rounding? Real men use a confidence interval anyway, so rounding is irrelevant.
Simon's Rock College
I once heard an anecdotal tale... Of an accountant, who had his wife balance the household checkbook (as a favor, so he wouldn't have to do the household paperwork as well as the paperwork from the house). 20 Years after she had been balancing the checkbook... The husband found out that she had been rounding to whole dollar amounts!!!
:)
In a hurried rush, he went through their records, and rebalanced the checkbook... After 20 years of rounding the difference he found: $.07 in their favor
I had to write an algorithm similar to this soon after I was hired at my current position. The reason the algorithm was needed was because when a dollar is split to pay part of three different charges, you have to give one charge the extra penny. Now imagine there are 21 charges, where some have higher priority than others, and they are all for random amounts, but if the person pays half, they want each bill to be paid off halfway.
Well, sometimes the rounding wasn't working out, one $10 charge would get paid $4.99, another $5.01, instead of each getting exactly $5. So I had to write something that would keep track of which accounts needed an extra penny to get to the even amount, and which had extra pennies to give. Then there was the "give-a-penny-take-a-penny" function that looked through them all and transferred money around to the account that needed it.
And yes, we've talked among ourselves to figure out if there's a way to steal small amounts of money as all this happens. The problem is we write reports that show where all the money went, and into which accounts, and we're all too lazy to change every report to ignore the special account where the money would go. Then there's the fact that we have to change the code every so often to deal with some new requirement, or improve performance, or something, so someone would certainly find it eventually. Then that means they have to be let in on the deal, and get a piece of the money.
Convergent rounding is used extensively in DSPs (its the best). Now it looks like the new term is Round-half-even.
Whoops, I forgot to hit the preview button.
.5 :(
float a = 0;
float b = 1;
for ( int i = 5000000; i > 0; i--)
{
a += 0.0000001;
b -= 0.0000001;
}
printf("a:%f\n",a);
printf("b:%f\n",b);
outputs:
a:0.476541
b:0.427965
Both should output
Right after they have been all listed, the USPTO will grant SCO patents on all of them!
Sent from my ASR33 using ASCII
One interesting example of mistakes with rounding errors was the Lonenz attractor which was an important part of the development of chaos thery. Lorenz first ran the simulation with one set of parameter and a few days later ran the simulation again, the original parameter values were printed out after rounding and hence different from the actual ones used. The second time he ran it he input the printed out values and came up with a very different solution. This showed the sensativity of dynamical systems to initial conditions.
There are four sorts of people in the world: fools, lunatics, idiots and morons. - Umberto Eco, Foucaut's pendulum.
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 perceived range (+/- 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...
Or Enron.
Round significantly up and harvest percentages.
Defining Statistics and Social Research
DSP was briefly mentioned in TFA. These days, most audio is recorded in 24 bits or more, but needs to be rounded to 16 bits to master on to CD. Simple truncation can cause harmonic sounds at low levels, so a high frequency (generally inaudible) noise is added to the signal. This is called dithering, and can make audible signals that would be truncated to zero. I've heard it happen. Even stranger is that the added noise peaks at 25-30dB louder than sound you can hear.
I’m old enough to remember 16K of memory being described as “whopping”
I remember a project ages ago (before the Pentium rounding bug). The customer (a state railway company) wanted to calculate fare tables. For that, they needed to be able to round up (2.1 -> 3), down (3.9 -> 3) and commercial (2.5 -> 3). Nothing too fancy so far. However, they also needed this operation to be carried out on PARTS of a currency unit - as in $0.20. Rounding up here would mean $3.04 -> $3.20. A typical scenario would look something like this : From 1-20km, the fare is number of kilometers multiplied by .32, rounded up to the next $0.10, then multiplied with a "class factor" of 1 for second and 1.5 for first class.
(And so on, and so on...)
Calculating a complete fare table at that time would take about 12 hours on a serious size Tandem computer.
(And of course, the program was written in a mix of COBOL and FORTRAN...)
Round-half-even thing was, if I recall correctly (it's been a while), the standard algorithm used when converting a float to an integer in Visual Basic. It was one of those things that got newbies quite confused at first, since they were either used to floor()-type rounding from working in other languages or the round-half-up they learned at school.
I don't get it.
Isn't that Square, not Round?
I encrypt all my files with Double XOR Encryption!
So yeah, use the rounding functions in .NET and you get bankers rounding.
Want to not use bankers rounding? Easy! convert it to a string first.
wait a minute, that can't be efficient, can it?
Any one know of an alternative?
I should have noted in my parent post that it is not to be construed as tax or financial advice. Consult an appropriate professional for your particular case.
You could've hired me.
As the word is derived from Welsh, it's spelled 'weird', not 'wierd'....
Q: What does the "H" in Jesus H. Christ stand for? A: Haploid.
You change part of the image, and the entire image gets dithered differently.
Bad for onMouseOvers, if you didn't notice the problem in time.
I'm still trying to figure out what people mean by 'social skills' here.
Troll? Btw. the troll of phaos looks great, I made it (or at least improved on the photograph of a sculpture).
I'm still trying to figure out what people mean by 'social skills' here.