[cairo] Banker's rounding problems and Nautilus
Daniel Amelang
daniel.amelang at gmail.com
Sat Dec 2 21:37:19 PST 2006
On 12/2/06, Daniel Amelang <daniel.amelang at gmail.com> wrote:
> #define CAIRO_MAGIC_NUMBER_FIXED_33_19 (12884901888.0)
> int
> _cairo_lround (double d)
> {
> union {
> double d;
> uint32_t ui32[2];
> } u;
>
> u.d = (d + 0.499999) + CAIRO_MAGIC_NUMBER_FIXED_33_19;
Whoops, that's supposed to be exactly 0.5, not 0.499999.
Unfortunately, it seems that even this approach has certain
pathological inputs that throw it off :( Regardless, it seems to mess
up much less than any other magic-number-derived approach that I've
tried. It's likelihood of producing "wrong" output is literally one in
a million (in my random test generator). Compare that to 228/million
for the original magic number approach, and 119/million for Bill's
approach. And the important case of exactly 0.5 is covered.
So, I personally don't think we'll get a magic number approach to ever
perform arithmetic rounding. But maybe we don't have to. Maybe
1/million is good enough, maybe Bill's 119/million is good enough. If
all we need is to cover the 0.5 case well, Bill's method covers it.
And of course, there is the option of falling back to my totally
different no-FP approach to _cairo_lround that I have for our
--disable-some-floating-point architectures. I just ran a quick perf,
and it seems to be fast enough on x86 that it doesn't affect the
overall performance on cairo-perf tests. The nice thing about this
no-FP approach is that it always uses true away-from-zero rounding.
It's just 2-3x slower than the current magic number approach,
although, like I said, it doesn't seem to make a difference in the
overall performance. It's still 5x faster than the original
floor(+0.5) approach.
On a side note, in his now famous "Know your FPU 2006 edition"
article, Sree Kotay drops some code that he claims performs arithmetic
rounding by adding another magic number to the input and then
performing the usual magic number trick. Basically the same idea that
we're exploring (except he doesn't shift at the end, because he
doesn't target an intermediate representation). It's the xs_RoundToInt
function on his page. So, I tested this function thoroughly, and it
turns out it _doesn't_ emulate arithmetic rounding either, he must
have just not tested it (enough). Just running it on the in-between
x.5 case from 0.5, 1.5, 2.5 on up shows it breaking down.
This is some bizarre stuff that I'm mucking with, so if anyone wants
to follow along and verify my conclusions, I'd appreciate it.
Dan
More information about the cairo
mailing list