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."
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
Why don't you guys have friends or journals?
This is what significant digits are for, though significant digit arithmetic uses probability to lower rounding error instead of forcing the user to do it himself.
After all, I am strangely colored.
Banker's rounding is just a naive implementation of significant digit arithmetic. http://en.wikipedia.org/wiki/Significance_arithmet ic
After all, I am strangely colored.
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
More like... nerdular nerdence!
My grandad tells me that he was taught to use round-half-even in the Royal Engineers back in WWII. One I've used which isn't in the list is stochastic rounding for all values (rather than just n+0.5) such that n+f (0 = f 1) rounds to n with probability (1-f) and (n+1) with probability f.
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 );
}
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
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"
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.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
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.
Program Intellivision!