$ clang -v
clang version 3.3 (tags/RELEASE_33/final)
Target: x86_64-apple-darwin12.4.0
double pow(double);
LLVM bitcode Assembly
// a*a*a*a*a*a
%1 = fmul double %a, %a | movaps %xmm0, %xmm1
%2 = fmul double %1, %a | mulsd %xmm1, %xmm1
%3 = fmul double %2, %a | mulsd %xmm0, %xmm1
%4 = fmul double %3, %a | mulsd %xmm0, %xmm1
%5 = fmul double %4, %a | mulsd %xmm0, %xmm1
ret double %5 | mulsd %xmm0, %xmm1
| movaps %xmm1, %xmm0
// a*a*a*a*a*a -ffast-math
%1 = fmul fast double %a, %a | mulsd %xmm0, %xmm0
%2 = fmul fast double %1, %1 | movaps %xmm0, %xmm1
%3 = fmul fast double %1, %2 | mulsd %xmm1, %xmm1
ret double %3 | mulsd %xmm0, %xmm1
| movaps %xmm1, %xmm0
// (a*a*a)*(a*a*a)
%1 = fmul fast double %a, %a | movaps %xmm0, %xmm1
%2 = fmul fast double %1, %a | mulsd %xmm0, %xmm0
%3 = fmul fast double %2, %2 | mulsd %xmm1, %xmm0
ret double %3 | mulsd %xmm0, %xmm0LLVM and GCC use the same algorithm for reassociation (and as far as i know, there is still no good literature on tradeoffs one way or the other), so you will get the same results, modulo some small differences implementation differences.
The reassociation passes exist mainly to promote redundancy elimination, and so the factorizations they perform are tilted towards making binary operations that look the same. Factorization and transformation into pow calls is also done, but this is just because it's easy to do :)
Note that the operations it forms may be "less than ideal" from a register pressure perspective, since it does not take this into account at the level reassociation is being performed (it assumes something will later reassociate them some other way if it wishes).
0.1 + 0.2 + 0.3 = 0.6000000000000000900
0.1 + (0.2 + 0.3) = 0.5999999999999999800
0.1 * 0.2 * 0.3 = 0.0060000000000000010
0.1 * (0.2 * 0.3) = 0.0060000000000000001
Using -ffast-math doesn't effect these results.Here's 0.1 + 0.2 + 0.3:
0.1 (0.1000000000000000055511151231257827021181583404541015625)
+ 0.2 (0.200000000000000011102230246251565404236316680908203125)
= 0.3000000000000000166533453693773481063544750213623046875
rounded: 0.3000000000000000444089209850062616169452667236328125
+ 0.3 (0.299999999999999988897769753748434595763683319091796875)
= 0.600000000000000033306690738754696212708950042724609375
rounded: 0.600000000000000088817841970012523233890533447265625
The operands can't be represented exactly as floating point so they are rounded to the nearest floating-point number before the addition even happens. And once the addition does happen, it is rounded to the nearest representable floating point value.Now we can look at the same for 0.1 + (0.2 + 0.3):
0.2 (0.200000000000000011102230246251565404236316680908203125)
+ 0.3 (0.299999999999999988897769753748434595763683319091796875)
= 0.500000000000000000000000000000000000000000000000000000
rounded: 0.500000000000000000000000000000000000000000000000000000
+ 0.1 (0.1000000000000000055511151231257827021181583404541015625)
= 0.6000000000000000055511151231257827021181583404541015625
rounded: 0.59999999999999997779553950749686919152736663818359375
It's interesting to note that the first addition ends up being exact! This is a bit lucky, because 0.5 is exactly representable in floating point and the initial operands got rounded in opposite directions. It's also interesting that 0.6... only turns into 0.599999... at the point that we round the answer.You can play around with this stuff conveniently using the Python "Decimal" module.
$ python
Python 2.7.5 (default, Aug 25 2013, 00:04:04)-
[GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from decimal import Decimal, getcontext
>>> getcontext().prec = 1000 # To prevent truncation/rounding
>>> Decimal(0.1)
Decimal('0.1000000000000000055511151231257827021181583404541015625')
>>> a = Decimal(0.1) + Decimal(0.2)
>>> a
Decimal('0.3000000000000000166533453693773481063544750213623046875')
>>> Decimal(float(a)) # get the value rounded to the nearest fp number
Decimal('0.3000000000000000444089209850062616169452667236328125')
You can also use my tool "dumpfp" (https://github.com/haberman/dumpfp) to inspect the value of a floating-point number in detail: $ ./dumpfp 0.1
Single Precision (IEEE 32-bit):
raw = 0x3dcccccd
sign = 0x0
exponent = 0x7b (-4)
significand = 0x4ccccd
VALUE CALCULATION =
significand (1 + 5033165/2^23 (1.60000002384185791015625))
* 2^exponent (2^-4)
= VALUE (13421773/2^27 (0.100000001490116119384765625))
Double Precision (IEEE 64-bit):
raw = 0x3fb999999999999a
sign = 0x0
exponent = 0x3fb (-4)
significand = 0x999999999999a
VALUE CALCULATION =
significand (1 + 1351079888211149/2^51 (1.600000000000000088817841970012523233890533447265625))
* 2^exponent (2^-4)
= VALUE (3602879701896397/2^55 (0.1000000000000000055511151231257827021181583404541015625)) Lua 5.2.2 Copyright (C) 1994-2013 Lua.org, PUC-Rio
> print(string.format(" 0.1 (%a)\n+ 0.2 (%a)\n= %a\n+ 0.3 (%a)\n= %a", 0.1,0.2,0.1+0.2, 0.3, 0.1+0.2+0.3))
0.1 (0x1.999999999999ap-4)
+ 0.2 (0x1.999999999999ap-3)
= 0x1.3333333333334p-2
+ 0.3 (0x1.3333333333333p-2)
= 0x1.3333333333334p-1
> print(string.format(" 0.2 (%a)\n+ 0.3 (%a)\n= %a\n+ 0.1 (%a)\n= %a", 0.2,0.3,0.2+0.3, 0.1, 0.2+0.3+0.1))
0.2 (0x1.999999999999ap-3)
+ 0.3 (0x1.3333333333333p-2)
= 0x1p-1
+ 0.1 (0x1.999999999999ap-4)
= 0x1.3333333333333p-1Edit: I see what you're doing now. I didn't appreciate enough how converting to decimals had such unpleasant effects :) Thanks.
From my experience, most programmers have a vague idea of how basic integers work, so that's not so surprising. (I'm in the group who only knows a little more than average about floating-point, but for what I do, I don't use FP math much either.)
x <fp_mul> y = (1+e)xy ; abs(e) <= u
The u ideally depends only on the FP format and rounding mode. I say ideally because library functions like sqrt may be less precise than the ideal (which is the result being equal to the exact value rounded according to the rounding mode). Note that the abstraction only as long as you don't go outside the range of normal exponents (it breaks when you reach infinity or subnormal).
EXAMPLE. Suppose we have a FP value L representing a length of something, and want to split it into segments no longer than the FP value M. Assume both integers are small enough to be representable in FP. The answer in exact arithmetic is:
N = ceil(L/M).
However if we evaluate this in FP, we may get a result N'<N for certain edge values. Which means one of the segment lengths we output will be greater than M!. So the result of the algorithm is incorrect!
We can fix it by multiplying (L/M) with a number sufficiently greater than one before the ceil, at the cost of sometimes deciding to split into one more segment than mathematically necessary. The fixed FP algorithm may then be:
N' = ceil(1.00005 <fp_mul> (L <fp_div> M))
After we apply the machine epsilon formulas we come to the conclusion that:
N' = ceil( (1+e1)(1+e2)1.00005 (L/M) ) ; abs(e1)<=u, abs(e2)<=u
We then show that:
(1+e1)(1+e2)*1.00005 >= 1.
This proves that what the algorithm gives to the ceil function is not less the exact value L/M, and that N'>=N. And ceil() can't make errors by definition, assuming the integer value is representable. QED
Why is this the case?
In order for ceil(L/M) to produce an incorrect result, we would need to have the mathematically exact result be of the form N + epsilon, with 0 < epsilon <= ulp(N)/2, and N an exact integer. But, can that ever actually happen? No. If it did, we would have a floating-point number L = M(N+epsilon) exactly, or L = MN + delta, with 0 < delta < ulp(MN)[1], which can never happen by the definition of ulp.
This illustrates a difficulty naive backwards-error analysis as commonly taught in numerical analysis courses. While it provides reasonable conservative bounds, which is often sufficient for engineering needs, it misses much of the subtlety of floating-point arithmetic, and leads people to take unnecessary steps to guard against “errors” that aren’t really there.
[1] Lemma: For any binary floating-point type, ulp(xy) > x ulp(y)/2.
Proof: First note that rounding of the product xy will only ever make ulp(xy) larger, so we can safely ignore it. Use the formula ulp(x) = 2^(floor(log2(x)) - P) where P is the precision in bits and expand:
ulp(x*y) = 2^(floor(log2(xy)) - P)
= 2^(floor(log2(x) + log2(y)) - P)
>= 2^(floor(log2(x)) + floor(log2(y)) - P)
= 2^(floor(log2(x)) ulp(y)
> 2^(log2(x) - 1) ulp(y) = x ulp(y)/2.If I wanted a correct bound for your revised problem, I would require that l be an upper bound on the true value (by forcing it to be rounded up earlier computations, for example) and that m be a lower bound on the true value. Then the simple computation delivers a correct result regardless of the magnitude of the error in l or m.
It's not naive. It's conservative, the exact opposite.
> it provides reasonable conservative bounds
It is the technique of backwards-error analysis that is naive, not the resulting bound. A “naive” method is not “simple” or “dumb” (or “aggressive” or whatever you think the opposite of “conservative” might be). It is simply a method that doesn’t use some a priori knowledge that’s available for the specific problem at hand. Backwards-error analysis is a naive technique in that it doesn’t benefit from specialized theorems of floating-point that allow one to establish tighter bounds, like the one I proved.
I gather (at least in your examples) that dealing with bigger numbers first typically affords more 'real' accuracy?
With arbitrary numbers a, b, and c, it would be a different story for a * b * c. Without further knowledge of a, b, c, there would be no particular reason to do the operations in one order or another, but the result of a * b * c and a * (b * c) could definitely differ by one ULP, probably by two in ordinary cases, by more if underflow occurred (but one of the variables would already have to be very small for this to happen).
It's not, except in the special case of one and the same number.
Look for the first occurrence of the word “commutative” in this page: http://en.wikipedia.org/wiki/Floating_point
But remember, if both the Wikipedia editors and I are wrong, you only need to produce one pair of operands a and b such that a * b does not produce not the same result(1) as b * a to be vindicated.
(1) I suggest we consider all NaN values to be “the same result” for the purpose of this challenge.
Consider storing a timestamp as a number of seconds since the epoch. We might use == to check if the timestamp has changed.
Knowing is better than fearing.
More seriously, I remember APL\360 SETFUZZ from long before many of you whippersnappers were born, which told the system to disregard so-many bits in an 'equals' evaluation.
FP implementations are generally evil, and errors cascade in irritating fashion. 50% of a numerical analysis class I took once was dedicated to error estimation. Stick to rationals if you can - it'll save your hairline.
Of course, most programmers only have a vague idea of how floating point numbers work. (I'm certainly among them!) It's very easy to run into problems. And even with a better understanding of the format, it's still very difficult to predict exactly what will happen in more complex expressions.
A really cool aside is that there are some relatively new toys we can use to model floating point numbers in interesting ways. In particular, several SMT solvers including Z3[1] now support a "theory of floating point" which lets us exhaustively verify and analyze programs that use floating point numbers. I haven't seen any applications taking advantage of this directly, but I personally find it very exciting and will probably try using it for debugging the next time I have to work with numeric code.
A little while back, there was an article about how you can test floating point functions by enumerating every single 32-bit float. This is a great way of thinking! However, people were right to point out that this does not really scale when you have more than one float input or if you want to talk about doubles. This is why SMT solvers supporting floating point numbers is so exciting: it makes this sort of approach practical even for programs that use lots of doubles. So you can test every single double or every single pair of doubles or more, just by being clever about how you do it.
I haven't tried using the floating point theories, so I have no idea how they scale. However, I suspect they are not significantly worse than normal bitvectors (ie signed/unsigned integers). And those scale really well to larger sizes or multiple variables. Assuming the FP support scales even a fraction as well, this should be enough to practically verify pretty non-trivial functions!
[1]: http://z3.codeplex.com/