06-05-2014, 11:03 AM

(06-05-2014 02:00 AM)Paul Dale Wrote: [ -> ](06-05-2014 01:18 AM)Claudio L. Wrote: [ -> ]I'd love to test some corner cases to see how the algorithms behave (like that case that needs 1600 digits, do you have any links to good material on this subject?). I did some tests of my own but I don't know what the corner cases are. I'd like to have some literature where they list cases that I can use to stress the algorithms and see the results.

I doubt that the 1600 bits (not digits) is actually required in reality. I suspect rather, that a proof was devised that this was sufficient for all possible input values rather than finding the absolute worst case. There has been a fair bit of work done on actually locating the worst cases in the past few years.

A quick check on google leads to two links:

For binary: http://hal.inria.fr/inria-00072594/PS/RR-4044.ps

For decimal: http://perso.ens-lyon.fr/damien.stehle/d...malexp.pdf

There are plenty of others a search away.

The example at the bottom of the second page of the second paper is interesting. Forty seven correct decimal digits being required to correctly round towards zero -- 34 plus 9 guards won't get this right and this is only a 16 digit input, a 34 digit one would be worse.

As I've said many times, "numerical analysis is hard".

- Pauli

Thanks for the links!

I will never understand this obsession for correct rounding. When rounding, you are introducing an error, so why obsess too much about it?

Case in point:

If I use 9 extra digits for internal calcs, then my result will only be affected by double rounding if my number is of the form:

nnnnn|499999999|5

Where nnnnn is digits we want to keep, the 4999 are my extra digits, and the last 5 belongs to the real number, is not stored anywhere and we don't really know it. That number could be a 5 or more.

So when rounding the higher precision numer, we'd turn the 49999999... into 500000.. causing the last digit to go off by one (insert your horror face here!).

But the magnitude of the error is:

With "correct" rounding e = -.4999999995

and with our "bad" result e = 0.5000000005

The last digit is not what we expected, so what? the number is still accurate within ~0.5 ULP and it will only happen 1 in 10^digits (when all 9 extra digits are exactly 499999999).

Honestly, I don't lose too much sleep about it, just because a mathematician doesn't get his way every now and then doesn't mean we should all go crazy about it.

But I'll test the algorithms and see what happens.

Thanks again for the links.

Claudio