Notions of Floating-Point Equality

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 (JLSv3 §15.21.1) 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:

  • equal

  • greater than

  • less than

  • unordered

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 that returns 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.

The BigDecimal class has a natural ordering that is inconsistent with equals; that is for at least some inputs bd1 and bd2,
c.compare(bd1, bd2)==0
has a different boolean value than
bd1.equals(bd2).3
In 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 BigDecimal specification 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 BigDecimal numbers with the same numerical value, but distinct pairs of scale (negation of the exponent) and unscaled value.

Comments:

There is also a surprising behaviour of "==" operator when it compares integer with float or long with double. In these cases integer operand is rounded to float and long operand is rounded to double.

int i = 0x1FFFFFF;
float f = 0x1p25f;
double d = 0x1p25;
i == f is true
f == d is true.
i == d is false

i < d is true

------------------

The Double.compare(double x, double y) corresponds to "totalOrder" predicate of the revised IEEE 754 standard.
totalOrder(x,y) == (Double.compare(x, y) <= 0) .

The revised IEEE 754 standard defines also 12 quiet comparison predicates and 10 signaling comparison predicates.

10 quiet predicates are well expressed by operators:

boolean compareQuietEqual(double x, double y) { return x == y; }
boolean compareQuietGreater(double x, double y) { return x > y; }
boolean compareQuietGreaterEqual(double x, double y) { return x >= y; }
boolean compareQuietLess(double x, double y) { return x < y; }
boolean compareQuietLessEqual(double x, double y) { return x <= y; }

boolean compareQuietNotEqual(double x, double y) { return !(x == y); }
boolean compareQuietNotGreater(double x, double y) { return !(x > y); }
boolean compareQuietLessUnordered(double x, double y) { return !(x >= y); }
boolean compareQuietNotLess(double x, double y) { return !(x < y); }
boolean compareQuietGreaterUnordered(double x, double y) { return !(x <= y); }

2 quiet predicates are expressed by Double.isNaN() .

boolean compareQuietUnordered(double x, double y) { return Double.isNaN(x) || Double.isNaN(y); }
boolean compareQuietOrdered(double x, double y) { return !Double.isNaN(x) && !Double.isNaN(y); }

10 signaling predicates can be expressed by such a method:

int compareSignalling(double x, double y) {
if (x < y) return -1;
if (x == y) return 0;
if (x > y) return +1;
throw new UnorderedException();
}

Then

boolean compareSignalingEqual(double x, double y) { return compareSignalling(x,y) == 0; }
boolean compareSignalingGreater(double x, double y) { return compareSignalling(x,y) > 0; }
boolean compareSignalingGreaterEqual(double x, double y) { return compareSignalling(x,y) >= 0; }
boolean compareSignalingLess(double x, double y) { return compareSignalling(x,y) < 0; }
boolean compareSignalingLessEqual(double x, double y) { return compareSignalling(x,y) <= 0; }

boolean compareSignalingNotEqual(double x, double y) { return !(compareSignalling(x,y) == 0); }
boolean compareSignalingNotGreater(double x, double y) { return !(compareSignalling(x,y) > 0); }
boolean compareSignalingLessUnordered(double x, double y) { return !(compareSignalling(x,y) >= 0); }
boolean compareSignalingNotLess(double x, double y) { return !(compareSignalling(x,y) < 0); }
boolean compareSignalingGreaterUnordered(double x, double y) { return !(compareSignalling(x,y) <= 0); }

Posted by nadezhin on February 27, 2010 at 12:11 AM PST #

@nadezhin,

Yes, the revised IEEE 754 standard defines many additional operations, some of which are easily expressed using existing constructs in the Java language and libraries. However, since the Java platform does not natively support the status flags, the quiet and signalling versions of operations would be the same as far as the Java platform is concerned.

Posted by Joe Darcy on March 04, 2010 at 07:03 AM PST #

Yes, the default exception handling in IEEE 754 is to raise status flag. As status flags are absent in Java, the default exception handling is empty.

The IEEE 754 standard describes alternative exception handling also. One of them is :
"Immediate transfer associated with a block: if the indicated exception is signaled, transfer control as soon as possible; no return is possible."

So I use the above "compareSignaling" pattern when I need the alternative exception handling.
As it is absent in native Java, I have to emulate it by Java UnorderedException.

The word "exception" is a little ambiguous here. IEEE exception is not the same as Java Exception.

----------

The status flags are absent in primitive Java types. However, it is possible to implement them in some numerical classes like arbitrary-precision numbers (BigDecimal, BigBinary). I'm curious about your opinion what is a better API style for status flags in these numerical classes:
- static variable
- thread-local variable
- instance field in MathContext class
- instance field in BigBinary class

Posted by nadezhin on March 05, 2010 at 12:36 AM PST #

Post a Comment:
Comments are closed for this entry.
About

darcy

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today
News

No bookmarks in folder

Blogroll