4 ms·
"It fails for x-y when x and y are close" I don't think that's quite right. Each individual operation is accurate within epsilon, the trouble with cancellatio
by CharlesHorsey 6y ago
"It fails for x-y when x and y are close"
I don't think that's quite right. Each individual operation is accurate within epsilon, the trouble with cancellation is that the error from operations prior to the subtraction is much larger than the result of the subtraction.
Example, if I do 1 + 2^30 - 2^30 in single precision I get zero. But each individual operation is correct. 1 + 2^30 = 2^30, so the error is 1 < 2^30 * epsilon. Then 2^30 - 2^30 = 0, which is exactly correct.
- fanf2 6y agoYes. The big errors appear when you remember x is actually (1+ε)x, as explained towards the end of the article. If you assume the inputs are exact then you get an accurate result, but if you are doing error analysis that does not help you.
- augustt 6y agoYep the term for this is catastrophic cancellation, which doesn’t invalidate the axiom.
- hpcjoe 6y agoThis is due to the non-associative nature of FP. (a+b) + c != a + (b+c). I disagree that the "axiom" as stated is fundamental. My main argument with it is that I don't see an easy way to go from the axiom to usable theorems about FP. Happy to be wrong on this, but I am missing this at this time.
- augustt 6y agoI'd say not only is fundamental, it's pretty much the only tool you have to start the analysis of an FP algorithm. If you want to analyze a naive sum algorithm for instance you do that by recursively applying the a ⊕ b = (a + b)(1 + ε) rule and figure out how the epsilons bubble up - the result being that the error is linear with the sum length.
- the_svd_doctor 6y agoThis is the right answer. Substraction is accurate, as much as it can be given the its inputs. It’s everything (combined) leading up to it that isn’t. Every year I struggle to teach this simple concept in class :-) :-(