9 ms·
Essential facts about floating point calculations
- thisisanacc 11y agoif( abs(x - y) < 1e-6 ). Testing for absolute error is often incorrect. Here is a better floating point comparator: http://floating-point-gui.de/errors/comparison/ http://floating-point-gui.de/errors/comparison/
- mortoray 11y agoI (the author) agree. I'm mainly trying to point out all the issues with floating point rather than give a full solution. I believe the problem stems from people just not realizing a lot of these problems. Certainly I'm not offering the complete solution here, and for any one of those points could spawn off several articles just to give ideas. So yes, links are appreciated so readers can get more into the details.
- danieldk 11y agoI thought we had to use ulps and (worst-case) error bounds specified by a library in ulps? https://en.wikipedia.org/wiki/Unit_in_the_last_place https://en.wikipedia.org/wiki/Unit_in_the_last_place http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html
- shoo 11y agoI am not sure I understand what you are saying exactly, but I believe in some circumstances you may be working with numerical values which you know to have errors > ulps. For example, suppose you working with data that you've obtained from some physical measurement, and your knowledge of the measurement process means you know it will have around 1% relative error. Or another example: suppose you are solving a linear system of equations Ax=b with highly precise right-hand-side data b (< \epsilon floating-point error), but the condition number of the matrix is large. Then perhaps it is only meaningful to expect the solution to be accurate to within k(A) \epsilon, the condition number of A. (I haven't thought about this stuff for a while, please correct me if this is wrong). edit: here's another reason. Suppose there's a heavy tradeoff between runtime and accuracy for some algorithm, so for some application it makes sense to use some cheap but somewhat inaccurate approximation. Then you're probably going to have and expect far larger errors. But, you might still be able to get some kind of (worst case?) bounds on the result, and want to assert something about that in test cases or sanity checks.
- exDM69 11y ago> Testing for absolute error is often incorrect True, but in this case it was to test for near-zero values so absolute error comparison is good enough. Here's a few macros I have been using to compare floating point values for approximate equality. It should be true if the values are equal to about 6-7 decimal places (in base-10). I use this in testing some code that deals with algorithms that have known numerical precision issues. The errors are inherent to the algorithms, not specifically floating point errors (e.g. solving Kepler's equation for near-parabolic trajectories). Note that it isn't specified whether "a" or "b" is the "gold" value to compare against, so it's measuring the relative error against a rough average of the two magnitudes. #define ZEROF(x) ((x)*(x) < DBL_EPSILON) #define EQF(a, b) ((ZEROF(a) && ZEROF(b)) || \ ZEROF(((a)-(b))*((a)-(b))/((a)*(a) + ((b)*(b))))) I am no scientist, so if anyone has improvement to the code above, I'll gladly take any feedback.
- stinos 11y agobut in this case it was to test for near-zero values so absolute error comparison is good enough Unless you are working with small numbers? Suppose you are dividing 1e-30 by 1e-30 than the result should still be 1 so if you return 0 when the second argument is < 1e-6 then you're screwed. I think boost's close_at_tolerance does what your macro tries to do; basically you say 'here's two numbers, check if their values differ no more than x% of their value' With the advantage that it is not a macro and guards against overflow etc: http://www.boost.org/doc/libs/1_37_0/boost/test/floating_point_comparison.hpp http://www.boost.org/doc/libs/1_37_0/boost/test/floating_poi....
- exDM69 11y ago> Unless you are working with small numbers? Suppose you are dividing 1e-30 by 1e-30 than the result should still be 1 so if you return 0 when the second argument is < 1e-6 then you're screwed. A very good point which I didn't think of! Obviously the 1e-6 figure is specific to the application. How should one avoid division by zero then? You can't figure out the relative error without a division, can you? For normal comparisons, using a relative error is the way to go but the zero case is different. On the other hand, using quantities of magnitudes in 1e-30 is already using half the exponent, a change of units may be due here.
- cnvogel 11y agoI've seen those "abs(fp_number)<some_tiny_value" in front of divisions, because people fear that the division will "blow up" in some way if a zero or sufficiently small number is passed to it. if (abs(q) >= 1e-6) rel_val = abs_val / q; else overflow_flag = true; But it's quite pointless, as the semantics of floating point calculations give you the indication about overflow right in the division result, it will be marked as positive or negative infinity. rel_val = abs_val / q; if (isnan(rel_val) || !finite(rel_val) || ans(rel_val) > some_limit) overflow_flag = true; (of course your FPU should be configured to not produce exceptions in the case of division by zero)
- arielb1 11y agoThat still won't prevent a zero-ish noisy `q` from causing a totally messed-up `rel_val`.
- kqr2 11y agoReference link to What Every Computer Scientist Should Know About Floating-Point Arithmetic : http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht...
- teddyh 11y agoFor anyone noticing the “Oracle” in the domain name: The same document used to be at http://docs.sun.com/source/806-3568/ncg_goldberg.html http://docs.sun.com/source/806-3568/ncg_goldberg.html
- stinos 11y agoI can't count the amount of times I see this text being posted. Yet it takes something like a degree in math/CS/... to read and understand it completely; it is really not suitable for everyone. As such I bookmarked Essential facts about floating point calculations so next time a psychologist or biologists comes asking me if I already knew matlab has a bug when comparing 0 to 0, I can point him/her to this document. And some proper code to compare floating point numbers using a relative error or so.
- deleted 11y ago[deleted]
- zubspace 11y agoA huge roadblock I recently ran into: It's possible, that floating operations may yield different results depending on the compiler or CPU architecture. As far as I know it's not possible to run a simulation depending on floats on different machines, expecting the same output. Some people recommend switching to integer operations and to keep floating point arithmetic to a minimum. Is this the only way to get deterministic math across machines? http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... Edit: I ran into this while trying to procedurally generate a map based on a seed value. Heightmap, zones/biomes, rivers, towns, etc are all based on a seed. The result must be completely reproducible on different machines, otherwise players would see different maps. The terrain is large and therefore chunked. There's a seed per chunk and only seeds of chunks visible to the client are sent to him. I now believe that the only way to implement this correctly is passing the full, complete state of a chunk to the player after the generation. There's no sane way to implement the whole generation with integer math only. But there's a positive side-effect: More traffic but less performance needed to regenerate the chunk on the client. Actually it's simpler to work around this problem in a physics simulation, because the authoritative server can simply sync the properties across the players frequently.
- pjc50 11y agoYou have to set compiler and runtime options to: - force IEEE compliance on - force Intel systems to disable extended-precision mode (80 bit internal registers) See e.g. http://stackoverflow.com/questions/6683059/are-floating-point-numbers-consistent-in-c-can-they-be http://stackoverflow.com/questions/6683059/are-floating-poin... Fixed-point integer is generally easier to handle but you have to do it "manually" as language support is scarce. And then watch out for overflow. It also may not be as fast as FP on modern systems (especially GPUs). Edit: one could write an alternate history where the first PC 3D accelerators were targeted at Quake and implemented fast fixed point. It was a common design decision for 3D engines. http://gamedev.stackexchange.com/questions/26823/why-did-the-old-3d-games-have-jittery-graphics http://gamedev.stackexchange.com/questions/26823/why-did-the... Arguably fixed-point's limitations are easier to understand. Floating will give you within epsilon of the "right" answer, but as we have seen this may vary in weird ways across platforms. Fixed will run into precision loss problems a lot earlier, forcing you to confront and deal with them. You also have to confront truncate vs. round earlier. A cite for "floating point is faster than fixed point": http://cboard.cprogramming.com/brief-history-cprogramming-com/4265-floating-point-faster-than-fixed-point.html http://cboard.cprogramming.com/brief-history-cprogramming-co...
- joosters 11y agoDespite what this page says, you can round-trip between floating point and strings. Take a look at: https://randomascii.wordpress.com/2012/03/08/float-precisionfrom-zero-to-100-digits-2/ https://randomascii.wordpress.com/2012/03/08/float-precision... Specifically, printf(“%1.8e”, f); ensures that a float will round-trip to decimal and back
- yoha 11y ago> It is possible to get the same number back though, even when using decimal. If the truncation length is simply extended long enough the parsing will yield the same number back. But I agree that actual code would have been clearer.
- mortoray 11y agoI do mention if you simply increase the length of the formatted string you can do round-trip. It should be noted however (as I do) that the decimal number is still not equivalent to the actual floating point number, only that when converted back it is the same. This point could, in theory, be an issue if your serialized form crosses systems that use different floating point systems.
- panic 11y agoIt should be noted however (as I do) that the decimal number is still not equivalent to the actual floating point number, only that when converted back it is the same. Since 2 divides evenly into 10, every binary number has an exact decimal representation, and you can produce a decimal string which is equivalent to any floating point number. You may need quite a few digits, though.
- brucedawson 11y agoIf you are trying to get exact compatibility between systems with different floating-point systems then serializing to text is the least of your problems.
- ucho 11y ago> Just consider that with 64-bit floats 0.3 + 0.6 = 8.9999999999999991. > It really took no effort at all to get a precision problem! That sure looks like serious precision problem :)
- mortoray 11y agoI suppose in hindsight my example doesn't look as disturbing as it's meant to. :) It's hard to show concise examples that truly show how this little bit of error eventually compounds and destabilizes a calculation.
- haberman 11y agoGood article! Just a couple corrections / comments: > n * x != x + … + x Not true if n == 2! For n = 2 they are exactly the same. Why is this? Because "n * 2" and "n + n" are both exactly one operation, which means they only get rounded once, and since both are mathematically identical they both get rounded to the same value. > I’m not sure why, but the default string formatting of floating point numbers in most languages, even domain-specific math languages, does not have high enough precision to store the complete number. I think it's probably related to the fact that printf() doesn't have any format specifiers for float that do What You Really Want, which is: print the shortest number that will parse back to the right value. So unless people want to implement this algorithm themselves (and, fascinatingly, the best known algorithm to do this was published only five years ago: http://dl.acm.org/citation.cfm?doid=1809028.1806623 http://dl.acm.org/citation.cfm?doid=1809028.1806623), you have to choose between having all your numbers be annoyingly long or losing precision for some numbers.
- Sharlin 11y ago> Not true if n == 2! For n = 2 they are exactly the same. Not true in many other cases either; a trivial example is n=1, or x=1 and n can be represented exactly. In all of the cases the "!=" in the headings is meant to be read "is not necessarily equal" or "there exist expressions e, e' for which e != e'"
- eru 11y ago> I think it's probably related to the fact that printf() doesn't have any format specifiers for float that do What You Really Want, which is: print the shortest number that will parse back to the right value. Lots of language support the proper behaviour these days. Haskell/ghc does, for example. [https://docs.python.org/3/tutorial/floatingpoint.html https://docs.python.org/3/tutorial/floatingpoint.html]: > Historically, the Python prompt and built-in repr() function would choose the one with 17 significant digits, 0.10000000000000001. Starting with Python 3.1, Python (on most systems) is now able to choose the shortest of these and simply display 0.1.
- panic 11y agoIn cases where the iteration can’t be avoided, it’s vital to understand you won’t get the expected result. A certain amount of rounding error will always accumulate. You can track the error and account for it during iteration to avoid errors accumulating. See, for example, Kahan summation: https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm
- lectrick 11y agoSee also "why I use integers whenever possible"
- lorddoig 11y agoMaybe I don't fully understand the issues at play here but I remember reading about so-called 'unums'[0], an alternative binary number representation that seems quite amazing. I don't understand why it doesn't get more attention, apart from the fact it would need to be supported in CPU hardware to be of any real use. [0]: http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPrecision1.pdf
- thewarrior 11y agoI recently ran into Minus Zero in javascript and was like WTF is MINUS zero ? https://en.wikipedia.org/wiki/Signed_zero https://en.wikipedia.org/wiki/Signed_zero Interesting stuff.
- nsajko 11y agoAnybody used decimal floating point? https://en.wikipedia.org/wiki/Decimal64_floating-point_format https://en.wikipedia.org/wiki/Decimal64_floating-point_forma...