Page 3 of 4
Posted: Mon Dec 15, 2008 11:16 pm
by sgt_baker
Thanks for all the help folks.
@Cashtoe: The 'problem value', as it were, is encountered when using an implementation of the Cumulative Density Function which has been pretty much industry standard for the past 20 years. If you're interested we can arrange to get together on TS or some such to have a look at the actual blurb. What I find suggests a CPU issue is that this exact code has been tested and found to work 100% of the time on numerous machines (MrC, Terr, my server, my workstation etc etc... ASGS being the one exception). Thanks for doing the legwork and checking the hex for the posted values, though.
Since I'm pretty certain that the precision issue is limited to ASGS, there is no need to provide additional results to the original post.
Posted: Tue Dec 16, 2008 1:30 am
by cashto
It's definitely the non-associativity of IEEE floating-point addition that is causing this. It's not a CPU or platform issue. To test it, I wrote a little program (in Erlang) that summed the numbers in every possible permutation (11! ~= 40 million ways). I got five distinct answers:
277.9052417046702
277.90524170467023
277.9052417046703
277.90524170467035
277.9052417046704.
(Note that I didn't get *exactly* the same numbers as you or everyone else, probably because I was using Erlang, which uses 64-bit doubles in memory but may or may not keep intermediate results at 80-bit precision. Also I have my doubts about the accuracy of the floating-point-to-decimal routine. I should try C and maybe strict FP see what I get).
Basically, every time the running sum goes over a power of two (32, 64, 128, 256) -- that's an opportunity to lose a bit of precision at the end.
Posted: Tue Dec 16, 2008 2:00 am
by Tigereye
cashto wrote:QUOTE (cashto @ Dec 15 2008, 03:18 PM) According to this
IEEE calculator:
277.90524170467012 = 4071 5E7B DEB9 C88
9
277.90524170467029 = 4071 5E7B DEB9 C88
C
So the error you are seeing is 3 ulps. That could easily be accounted for due to the non-associative property of machine floating-point.
In English, everyone's elses compiler is doing the math exactly as you asked for it -- left to right. But since you're using SQL, under the hood the database might be fetching and/or computing the numbers in some random order.
My suggestion is that if an error as small as 3 ulps in an intermediate calculation results in a 50% change in the final result, then whatever algorithm you are using is highly succeptible to rounding error; you need to do some numerical analysis (for example, using
interval arithmetic) to determine where you are losing precision.
Edit: I meant non-associative, not non-commutative.
I think cashto wins the cookie
--TE
Posted: Tue Dec 16, 2008 2:06 am
by sgt_baker
And some more to boot
Posted: Tue Dec 16, 2008 4:32 am
by cashto
For more numerical analysis fun:
Kahan summation algorithm -- summing long lists of numbers "the right way".
Loss of signifigance -- catastrophic cancellation occurs when subtracting two roughly equal numbers (& how to avoid it).
What every computer scientist should know about floating-point arithmetic.
Posted: Tue Dec 16, 2008 6:31 am
by logsniffer
If performance isn't an issue just stringify the number and do string arithmetic.
Posted: Tue Dec 16, 2008 7:28 am
by Picobozo
SMART PEOPLE SHUT UP.
NOSE BLEED!!!
Posted: Tue Dec 16, 2008 5:32 pm
by madpeople
cashto wrote:QUOTE (cashto @ Dec 16 2008, 01:30 AM) It's definitely the non-associativity of IEEE floating-point addition that is causing this. It's not a CPU or platform issue. To test it, I wrote a little program (in Erlang) that summed the numbers in every possible permutation (11! ~= 40 million ways). I got five distinct answers:
277.9052417046702
277.90524170467023
277.9052417046703
277.90524170467035
277.9052417046704.
(Note that I didn't get *exactly* the same numbers as you or everyone else, probably because I was using Erlang, which uses 64-bit doubles in memory but may or may not keep intermediate results at 80-bit precision. Also I have my doubts about the accuracy of the floating-point-to-decimal routine. I should try C and maybe strict FP see what I get).
Basically, every time the running sum goes over a power of two (32, 64, 128, 256) -- that's an opportunity to lose a bit of precision at the end.
I was just going to sudggest doing that, `ym on pre-emptivly fufilling my sudggestion
Posted: Wed Dec 17, 2008 12:20 am
by MrChaos
42
MrChaos' brain
Posted: Wed Dec 17, 2008 2:04 am
by ryjamsan
Deschain wrote:QUOTE (Deschain @ Dec 16 2008, 05:38 AM) Result = 10
Using: fingers
Nothing made me laugh more than this response. And I really needed a GOOD LAUGH