Re: [math-fun] equality of floating point numbers.
Ray Tayek writes: << hi, reading junit recipies by martin fowler. talking about equality as an equivalence relation on objects. if one of the fields of the objects that is in included in the equals method has a floating point number, then one uses some idea of "close enough" (i.e. within some epsilon). this is clearly reflexive and symmetric, but not transitive. he conjectures that this idea of "close enough" is the *only* case (in the space of equals methods for object) of having a equals relation that is symmetric and reflexive and not transitive. does anyone have a counter example?
It's hard to know what is meant here by "an equals relation", since in math the concept of an "equivalence relation" is defined by possessing reflexivity, symmetry, and transitivity. It's easy to come up with a relation having the first two properties but not transitivity: Let the set on which the relation is defined be {A, B, C}. Let the entire relation be defined by A~A, B~B, C~C, A~B, B~A, B~C, and C~B. Then ~ is easily seen to be reflexive and symmetric, but not transitive (A~B and B~C but not A~C). This minimal example can be transplanted to any set S havng at least 3 elements, such as all real numbers: Pick 3 elements from S, call them A,B,C, and define ~ among A,B,C just as above. Let all other elements X satisfy X ~ X but no other "~" statement. Then you again have reflexivity and symmetry but not transitivity (since only one counterexample is needed). I don't know what it would mean to say this is or is not a "close enough" example. --Dan
This seems to be a question about word usage, rather than a mathematically precise question. Any use I have ever seen in a purely mathematical context does refer only to an equivalence relation, which must thus be transitive. In a programming context, non-transitively can happen by accident in an object-oriented language, if one creates two classes that know how to compare themselves to a third, but not to each other. E.g., Rational, Float, and Integer; 2/1 = 2, 2.0 = 2, but 2/1 != 2.0. Another programming example is where one has two String classes, one using case sensitive compares, and one using case insensitive compares. If one implements comparisons between the two classes as either a case sensitive or a case insensitive compare, the result will not be transitive. I think other strange things can happen with case insensitive compares in some systems. Franklin T. Adams-Watters -----Original Message----- From: dasimov@earthlink.net Ray Tayek writes: << hi, reading junit recipies by martin fowler. talking about equality as an equivalence relation on objects. if one of the fields of the objects that is in included in the equals method has a floating point number, then one uses some idea of "close enough" (i.e. within some epsilon). this is clearly reflexive and symmetric, but not transitive. he conjectures that this idea of "close enough" is the *only* case (in the space of equals methods for object) of having a equals relation that is symmetric and reflexive and not transitive. does anyone have a counter example?
It's hard to know what is meant here by "an equals relation", since in math the concept of an "equivalence relation" is defined by possessing reflexivity, symmetry, and transitivity. It's easy to come up with a relation having the first two properties but not transitivity: Let the set on which the relation is defined be {A, B, C}. Let the entire relation be defined by A~A, B~B, C~C, A~B, B~A, B~C, and C~B. Then ~ is easily seen to be reflexive and symmetric, but not transitive (A~B and B~C but not A~C). This minimal example can be transplanted to any set S havng at least 3 elements, such as all real numbers: Pick 3 elements from S, call them A,B,C, and define ~ among A,B,C just as above. Let all other elements X satisfy X ~ X but no other "~" statement. Then you again have reflexivity and symmetry but not transitivity (since only one counterexample is needed). I don't know what it would mean to say this is or is not a "close enough" example. --Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
At 09:14 PM 4/19/2006, you wrote:
This seems to be a question about word usage, rather than a mathematically precise question. ...
yes
In a programming context, non-transitively can happen by accident in an object-oriented language, if one creates two classes that know how to compare themselves to a third, but not to each other. E.g., Rational, Float, and Integer; 2/1 = 2, 2.0 = 2, but 2/1 != 2.0.
yes, but that works by overloading ==.
Another programming example is where one has two String classes, one using case sensitive compares, and one using case insensitive compares. If one implements comparisons between the two classes as either a case sensitive or a case insensitive compare, the result will not be transitive. I think other strange things can happen with case insensitive compares in some systems.
yes, we came up with something like that in our study group tonight, involving strings in different languages or from different code pages, but could not think of any other. i was hoping for a counter example from math that might end up in a random application. thanks
Franklin T. Adams-Watters
-----Original Message----- From: dasimov@earthlink.net
Ray Tayek writes:
<< hi, reading junit recipies by martin fowler. talking about equality as an equivalence relation on objects. ... he conjectures that this idea of "close enough" is the *only* case ... does anyone have a counter example?
It's hard to know what is meant here by "an equals relation", ... It's easy to come up with a relation having the first two ... properties but not transitivity: ... I don't know what it would mean to say this is or is not a "close enough" example. ...
--- vice-chair http://ocjug.org/
Franklin T. Adams-Watters wrote:
In a programming context, non-transitively can happen by accident in an object-oriented language, if one creates two classes that know how to compare themselves to a third, but not to each other. E.g., Rational, Float, and Integer; 2/1 = 2, 2.0 = 2, but 2/1 != 2.0.
...and Ray Tayek responded:
yes, but that works by overloading ==.
But Ray, your original question was based on comparing floating-point numbers using |a-b|<epsilon, which is itself redefining the equality operator! The "real" equality operation on floating-point values is one that requires perfect matching, which is flawed in the opposite direction: too *few* things are equal, not too many. (When the "true" answer to some computation is not perfectly representable by your favorite floating-point scheme, two mathematically equivalent but computationally distinct evaluation techniques might result in non-identical answers. For instance, C tells me that (1/10)^2 != 1/100.) The problem here isn't with equality, it's with the associative and distributive laws for the arithmetic operations that generated the numbers in the first place. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (4)
-
dasimov＠earthlink.net -
franktaw＠netscape.net -
Michael Kleber -
Ray Tayek