Notions of Floating-Point Equality
By darcy on Feb 25, 2010
Moving on from identity and equality of objects, different notions of equality are also surprisingly subtle in some numerical realms.
As comes up from time to time and is often surprising, the "
==" operator defined by IEEE 754 and used by Java for comparing floating-point values
is not an equivalence relation. Equivalence relations satisfy three properties, reflexivity (something is equivalent to itself), symmetry (if a is equivalent to b, b is equivalent to a), and transitivity (if a is equivalent to b and b is equivalent to c, then a is equivalent to c).
The IEEE 754 standard defines four possible mutually exclusive ordering relations between floating-point values:
A NaN (Not a Number) is unordered with respective to every floating-point value,
including itself. This was done so that NaNs would not quietly slip by without due notice. Since (NaN == NaN) is false, the IEEE 754 "
==" relation is not an equivalence relation since it is not reflexive.
An equivalence relation partitions a set into equivalence classes; each member of an equivalence classes is "the same" as the other members of the classes for the purposes of that equivalence relation. In terms of numerics, one would expect equivalent values to result in equivalent numerical results in all cases. Therefore, the size of the equivalence classes over floating-point values would be expected to be one; a number would only be equivalent to itself. However, in IEEE 754 there are two zeros, -0.0 and +0.0, and they compare as equal under
==. For IEEE 754 addition and subtraction, the sign of a zero argument can at most affect the sign of a zero result. That is, if the sum or difference is not zero, a zero of either sign doesn't change the result. If the sum or differnece is zero and one of the arguments is zero, the other argument must be zero too:
-0.0 + -0.0 ⇒ -0.0
-0.0 + +0.0 ⇒ +0.0
+0.0 + -0.0 ⇒ +0.0
+0.0 + +0.0 ⇒ +0.0
Therefore, under addition and subtraction, both signed zeros are equivalent. However, they are not equivalent under division since 1.0/-0.0 ⇒ -∞ but 1.0/+0.0 ⇒ +∞ and -∞ and +∞ are not equivalent.1
Despite the rationales for the IEEE 754 specification to not define
== as an equivalence relation, there are legitimate cases where one needs a true equivalence relation over floating-point values, such as when writing test programs, and cases where one needs a total ordering, such as when sorting. In my numerical tests I use a method
true for two floating-point values x and y if:
((x == y) &&
(if x and y are both zero they have the same sign)) ||
(x and y are both NaN)
Conveniently, this is just computed by using
(Double.compare(x, y) == 0). For sorting or a total order, the semantics of
Double.compare are fine; NaN is treated as being the largest floating-point values, greater than positive infinity, and -0.0 < +0.0. That ordering is the total order used by by
java.util.Arrays.sort(double). In terms of semantics, it doesn't really matter where the NaNs are ordered with respect to ther values to as long as they are consistently ordered that way.2
These subtleties of floating-point comparison were also germane on the Project Coin mailing list last year; the definition of floating-point equality was discussed in relation to adding support for relational operations based on a type implementing the
Comparable interface. That thread also broached the complexities involved in comparing BigDecimal values.
BigDecimal class has a natural ordering that is inconsistent with equals; that is for at least some inputs
has a different boolean value than
BigDecimal, the same numerical value can have multiple representations, such as (100 × 100) versus (10 × 101) versus (1 × 102). These are all "the same" numerically (
compareTo == 0) but are not
equals with each other. Such values are not equivalent under the operations supported by
BigDecimal; for example (100 × 100) has a scale of 0 while (1 × 102) has a scale of -2.4
While subtle, the different notions of numerical equality each serve a useful purpose and knowing which notion is appropriate for a given task is an important factor in writing correct programs.
1 There are two zeros in IEEE 754 because there are two infinities. Another way to extend the real numbers to include infinity is to have a single (unsigned) projective infinity. In such a system, there is only one conceptual zero. Early x87 chips before IEEE 754 was standardized had support for both signed (affine) and projective infinities. Each style of infinity is more convenient for some kinds of computations.
2 Besides the equivalence relation offered by
Double.compare(x, y), another equivalence relation can be induced by either of the bitwise conversion routines, Double.doubleToLongBits or Double.doubleToRawLongBits. The former collapses all bit patterns that encode a NaN value into a single canonical NaN bit pattern, while the latter can let through a platform-specific NaN value. Implementation freedoms allowed by the original IEEE 754 standard have allowed different processor families to define different conventions for NaN bit patterns.
3 I've at times considered whether it would be worthwhile to include an "
@NaturalOrderingInconsistentWithEquals" annotation in the platform to flag the classes that have this quirk. Such an annotation could be used by various checkers to find potentially problematic uses of such classes in sets and maps.
4 Building on wording developed for the
BigDecimalspecification under JSR 13, when I was editor of the IEEE 754 revision, I introduced several pieces of decimal-related terminology into the draft. Those terms include preferred exponent, analogous to the preferred scale from
BigDecimal, and cohort, "The set of all floating-point representations that represent a given floating-point number in a given floating-point format." Put in terms of
BigDecimal, the members of a cohort would be all the
BigDecimalnumbers with the same numerical value, but distinct pairs of scale (negation of the exponent) and unscaled value.