Comparing Floating-Point Numbers Is Tricky(bitbashing.io) |
Comparing Floating-Point Numbers Is Tricky(bitbashing.io) |
Specifically: when you have a less-than relationship "<", then !(a<b) && !(b<a) implies that a and b are equal (a==b). And if a==b and b==c then it must be the case that a==c, or the requirements of the ordering predicate are not met. Unfortunately, under most of these FP comparison schemes, for numbers a and b that are "close but not too close", it's the case that a<b, but for x=(a+b)/2, a==x and x==b!
When the float is first inserted into the set/map it has 80 bit precision, but that gets truncated to float or double precision during the store. This breaks the ordering as you are saying, but it's not an inherent flaw with floats as such.
The problem goes away if you compile with -mfpmath=sse because then the math will be performed in the same precision as the storage format.
Bug #323 is responsible for a huge amount of mistrust of floats that they don't deserve. Other compilers don't have this problem because they truncate the floats before any comparison.
The "bug" is x87 design, period. And x87 is the past. It's old, and bad. SSE and IEEE 754 is the present.
¬(a<b) ∧ ¬(b<a) → a=b is not, in fact, a requirement on <. Rather, the point is that behind the scenes, any two elements satisfying ¬(a<b) ∧ ¬(b<a) are treated as equivalent by these containers.
To see the difference, consider the (somewhat counter-intuitive) behavior of NaNs: for any two NaNs m, n, we have ¬(m<n) and ¬(n<m), yet also m≠n. If that implication were an actual requirement, then the usual ordering < on floats would not be a suitable ordering predicate. What happens, though, is that the containers will implicitly treat NaNs as equivalent, i.e., the notion of equivalence the container uses for the elements depends only on < and might not coincide with the usual ==.
I was using C++'s std::sort and soon enough things would go wrong. It would crash at unpredictable times, I suspected I was corrupting memory somewhere. Parts of my data structures would get overwritten by parts from some other data structure. I checked and checked and checked my code, nothing seemed wrong.
Its only after opening the covers, when I started peering into the sort that I realized my mistake. I was passing the comparison operator that was a "less than equal" relation.
If you're ever doing mathematical calculations of any sort, it is a good practice to have a handle on the scale your numbers will lie within. If not just to be a better professional, it helps you choose an ϵ that matches.
(The above bug is a restatement of bubblethink's sibling comment; it's an inequality where the two values are extremely (exactly!) close.)
The Go bug on the lack of a round function had several broken implementations, none of which had a direct equality[1].
3.1415927410125732421875 equals 3.1415927410125732421875
The problem is that programmers expect the float to be a decimal (smaller than the float) or integer.
For example if you want to calculate that two vectors are parallel then comparing for lesser or greater won't give you the expected result if you need them to be zero in difference. You might think that the vectors (0, 10) and (10, 10) are parallel but using !(x > 0 || x < 0) won't help you. You still end up using a threshold of the smallest float, something like (abs(x - 0) < 0.0000000000000000000001)
where the key takeaway is that between -1 -> 1 is where the %50 of floats live.
https://randomascii.wordpress.com/2013/07/16/floating-point-...
The hard part is understanding when it is appropriate to compare floating point numbers and how to produce them.
I regularly use floating point numbers as keys in dictionaries and of course all the code quality tools whine about comparisons being inexact. But in my case there is no fuzziness because the keys are all produced by the same method and hence do not suffer from any different rounding errors.
Pretty much every new member of the team sees floats being compared and has heart attack yet the code in question is in the oldest and most reliable component of the whole million line program.
Just don't expect two numbers produced by different expressions that would be mathematically equivalent but have operators in a different order to produce identical results.
What I would say is that when you're considering comparison of floating point numbers, it's important to understand what the operation means in terms of the data which you're representing using the floating point numbers, in other words what does it mean in terms of the data for two values to be equal or not equal. Usually there is a precision inherent in the data itself which will guide you to how to formulate equality, if necessary.
bool zero(float x) ( return x*x < FLT_EPSILON; }
bool equal_float(float a, float b) {
return (zero(a) && zero(b)) || // both are zero
zero((a-b)*(a-b) / (a*a + b*b)); // or relative error squared is zero
}
Critique and comments welcome.
A better comparison would check for zero somehow like this:
bool zero(float x) { return std::abs(x) <= std::abs(x)*FLT_EPSILON; }I typically use this with doubles and DBL_EPSILON, which is much much smaller than FLT_EPSILON.
With FLT_EPSILON this roughly equals to "zero" being "less than 0.001". If the zero check is omitted, there's going to be a division by near-zero which will make the results nonsense (and you have to draw the line somewhere). With DBL_EPSILON "zero is less than 0.000000001".
If this is too loose, then `zero(x) = abs(x) < FLT_EPSILON` makes it much stricter (about 1e-7).
This is good enough for my purposes, I don't deal with very small numbers in float and doubles give more than enough precision.
NOTE: I usually use this kind of comparison in testing by comparing known "gold" figures against the results of the code being tested. I don't test accuracy, I test for "in the ballpark" because the stuff I deal with has built-in inaccuracy in the algorithm and numerics.
The version you posted will always return false if I read it correctly.
http://blogs.mathworks.com/cleve/2014/07/07/floating-point-n...
Floats are great for quick, mostly correct, math.
Think REALLY carefully about any process that then 'compares' the result. Usually you're "doing it wrong" if that's the case.
I think I might even find it useful if compilers could be instructed to warn whenever comparison operators were used on a float type value.
pg1:joel=#* select 1/7::numeric7; ?column? ------------------------ 0.99999999999999999998 (1 row)
pg1:joel=# select 1/7::float*7; ?column? ---------- 1 (1 row)
Numeric types are meant to be exact, so they will be represented as an exact value.
What language does this? It is more likely that it is printing out a truncated form but the number still contains that small difference, such as it will print "1.1" even though 1.1 isn't exactly representable in binary. This comes from the often used Grisu set of algorithms for printing which (in Grisu3) prints the smallest string that can represent the floating point bit pattern.
http://www.russinoff.com/papers/ieee.pdf
For something more concrete, consider Section 8, "Variations Allowed by the IEEE Floating-Point Standard", of the TestFloat tool for testing floating point implementations for IEEE compliance:
http://www.jhauser.us/arithmetic/TestFloat-3c/doc/TestFloat-...
And of course, many arithmetic operations (e.g., trig functions) aren't even covered by the standard, which occasionally provokes consternation like this...
https://forums.theregister.co.uk/forum/1/2014/10/10/intel_un...
Also the standard does specify trig functions (§9.2 Recommended correctly rounded functions), but that's one of the optional parts, and as far as I know no one has actually implemented them fully (CRlibm came close, but I don't think their pow function has been fully proven to be correctly rounded, and in any case it isn't widely used).
This is actually a big problem with most standards: a lot of them contain finicky details about which only a very small subset of people care. As far as I know, there still isn't a C compiler that implements all the PRAGMAs specified in the C-1999/C-2011 specs.