4 ms·
This “fundamental axiom” is not true: ”This means that for any two floating point numbers, say x and y, any operation involving them will give a floating point
by fanf2 6y ago
This “fundamental axiom” is not true:
”This means that for any two floating point numbers, say x and y, any operation involving them will give a floating point result which is within a factor of 1+ϵ of the true result.”
It fails for x-y when x and y are close. Subtraction is the easiest way to get big floating point errors. The article does mention this towards the end but you need to wade through a lot of equations before you get told this very important caveat.
The more tricky way to accumulate errors is to add lots of small numbers to a big number. Just summing a list of floats can be fraught with peril! Kahan’s summation algorithm is enlightening: https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm
- lifthrasiir 6y agoKahan summation is unfortunately slower than naive summation, which can be problematic. Pairwise summation [1], which roundoff error is proportional to log n, can be used as a drop-in replacement of naive summation as it performs more or less equally. [1] https://en.wikipedia.org/wiki/Pairwise_summation https://en.wikipedia.org/wiki/Pairwise_summation
- 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 :-) :-(
- imurray 6y ago> Kahan’s summation algorithm Radford Neal (2015) has an approach to computing sums exactly (to the correct rounded floating point number) in less than twice the time to do it naively. In some situations it can do work in parallel and saturate memory bandwidth, so takes roughly the same time: http://www.cs.toronto.edu/~radford/xsum.abstract.html http://www.cs.toronto.edu/~radford/xsum.abstract.html "Kahan’s (1965) method for reducing summation error (but without producing the exact result) was also tested on all systems. On modern 64-bit processors, computing the exact sum with the large superaccumulator method was faster than Kahan’s method for summations of more than about 1000 terms. Kahan’s method was significantly faster than the small superaccumulator method only for summations of less than about 100 terms."
- vortico 6y agoI think you're misinterpretating the fundamental axiom because it's still true for `x-y`. What you're thinking is that the fundamental axiom applies to the composition of operations `closest_float(x) + closest_float(y)`, but the axiom only applies to each individual operation. The axiom can be stated more rigorously "If f is a (possibly multivariate) function on the set of floats to the reals, the IEEE-compliant approximation of f must give the closest float for all float values of its arguments."
- tgb 6y agoThey're correct that the "In mathematical terms" version of it is wrong (even for addition, if one is negative). It's missing fl()'s around the other a's and b's. Your statement is greatly superior than the poor man's version presented in the article.
- zozbot234 6y ago> "If f is a (possibly multivariate) function on the set of floats to the reals, the IEEE-compliant approximation of f must give the closest float for all float values of its arguments." It should be noted that this is not exactly true for some IEEE functions, due to the table-maker's dilemma: computing the "closest float approximation" to an arbitrary function can be computationally infeasible if the true result is close to being halfway in-between two consecutive floats. (This applies to the default rounding mode, but can be extended by analogy to other rounding modes.)
- dragontamer 6y ago> It fails for x-y when x and y are close. Subtraction is the easiest way to get big floating point errors. And note: addition might be subtraction, while subtraction might be addition. Consider x=1.0 and y=-0.99999. x + y = 0.00001 You did addition, but you got cancellation error. The only solution is to sort the numbers from largest to smallest dynamically during runtime.
- dreamcompiler 6y agoIn other words, while we all know that addition and subtraction over real numbers is associative, addition and subtraction over floating point numbers is not.
- commandlinefan 6y ago> Subtraction is the easiest way to get big floating point errors. That's why most modern floating point representations allow subnormal numbers: without them, subtracting two near, normal numbers will result in zero even if the numbers aren't equal.
- deleted 6y ago[deleted]
- the_svd_doctor 6y agoThat's not true. The axiom is correct. Say you're using double (i.e., you have 16 decimal digits of accuracy, roughly) and you are doing ((1.0 + 1e-20) - 1.0). That becomes (1.0 - 1.0) = 0.0 because 1e-20 was dropped during the addition. The substraction was perfectly accurate given its inputs (1.0 - 1.0 is exactly 0.0). The issue is that float(1.0 + 1e-20) = 1.0. But that's also very accurate ! (All the 16 decimal digits of 1.0 are correct). But yeah the 20th (decimal) digit got dropped. You see how each individual computation is maximally accurate. So the axiom is correct. What it boils down to is that you are manipulating (adding/subtracting) numbers of very different magnitudes. So cancellations, which would be negligible if all numbers where of similar magnitude, becomes catastrophic. Hence the name catastrophic cancellations.
- stephencanon 6y agoThe key is the framing; as stated, x and y are _exact_ floating-point values, which makes the statement true[1]. In fact, it's embarrassingly trivial, since it is just a weakening of the definition of rounding used by IEEE 754. In particular, if cancellation occurs in x - y, then the result is exact (Sterbenz' lemma). [1] Under the assumption that no underflow or overflow occurs (which is the usual framing for this sort of naive error analysis). It's easy enough to correct for underflow by adding an absolute error term as well.