* Elisp manual, node "Comparison of Numbers"
@ 2006-05-29 13:20 Drew Adams
2006-05-29 13:33 ` David Kastrup
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Drew Adams @ 2006-05-29 13:20 UTC (permalink / raw
I blindly got bit by this one. The Elisp manual gives this as an example of
how to test near equality of floating-point numbers:
(defvar fuzz-factor 1.0e-6)
(defun approx-equal (x y)
(or (and (= x 0) (= y 0))
(< (/ (abs (- x y))
(max (abs x) (abs y)))
fuzz-factor)))
When either x or y is 0.0, but not both, this gives nil no matter how close
the other number is to zero. I think this is more like what is needed:
(defun approx-equal (x y &optional fuzz)
(setq fuzz (or fuzz 1.0e-8))
(cond ((= x 0.0) (< y fuzz))
((= y 0.0) (< x fuzz))
(t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:20 Elisp manual, node "Comparison of Numbers" Drew Adams
@ 2006-05-29 13:33 ` David Kastrup
2006-05-29 13:42 ` Kim F. Storm
2006-05-29 21:28 ` Richard Stallman
2006-05-29 13:40 ` Lennart Borgman
2006-05-29 19:23 ` Stefan Monnier
2 siblings, 2 replies; 13+ messages in thread
From: David Kastrup @ 2006-05-29 13:33 UTC (permalink / raw
Cc: Emacs-Devel
"Drew Adams" <drew.adams@oracle.com> writes:
> I blindly got bit by this one. The Elisp manual gives this as an example of
> how to test near equality of floating-point numbers:
>
> (defvar fuzz-factor 1.0e-6)
> (defun approx-equal (x y)
> (or (and (= x 0) (= y 0))
> (< (/ (abs (- x y))
> (max (abs x) (abs y)))
> fuzz-factor)))
>
> When either x or y is 0.0, but not both, this gives nil no matter how close
> the other number is to zero. I think this is more like what is needed:
>
> (defun approx-equal (x y &optional fuzz)
> (setq fuzz (or fuzz 1.0e-8))
> (cond ((= x 0.0) (< y fuzz))
> ((= y 0.0) (< x fuzz))
> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
The problem here is that fuzz is a _relative_ measure of equality, and
you employ it as an absolute measure here. I don't think it a good
idea at all that 1e-12 and 0.995e-12 are considered different, while
1e-8 and 0.0 are considered equal.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:20 Elisp manual, node "Comparison of Numbers" Drew Adams
2006-05-29 13:33 ` David Kastrup
@ 2006-05-29 13:40 ` Lennart Borgman
2006-05-29 18:14 ` Drew Adams
2006-05-29 19:23 ` Stefan Monnier
2 siblings, 1 reply; 13+ messages in thread
From: Lennart Borgman @ 2006-05-29 13:40 UTC (permalink / raw
Cc: Emacs-Devel
Drew Adams wrote:
> I blindly got bit by this one. The Elisp manual gives this as an example of
> how to test near equality of floating-point numbers:
>
> (defvar fuzz-factor 1.0e-6)
> (defun approx-equal (x y)
> (or (and (= x 0) (= y 0))
> (< (/ (abs (- x y))
> (max (abs x) (abs y)))
> fuzz-factor)))
>
> When either x or y is 0.0, but not both, this gives nil no matter how close
> the other number is to zero. I think this is more like what is needed:
>
> (defun approx-equal (x y &optional fuzz)
> (setq fuzz (or fuzz 1.0e-8))
> (cond ((= x 0.0) (< y fuzz))
> ((= y 0.0) (< x fuzz))
> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
>
>
Looks reasonable, but you have to use
(< (abs y) fuzz)
etc.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:33 ` David Kastrup
@ 2006-05-29 13:42 ` Kim F. Storm
2006-05-29 13:54 ` Lennart Borgman
2006-05-29 21:28 ` Richard Stallman
1 sibling, 1 reply; 13+ messages in thread
From: Kim F. Storm @ 2006-05-29 13:42 UTC (permalink / raw
Cc: Drew Adams, Emacs-Devel
David Kastrup <dak@gnu.org> writes:
> "Drew Adams" <drew.adams@oracle.com> writes:
>
>> I blindly got bit by this one. The Elisp manual gives this as an example of
>> how to test near equality of floating-point numbers:
>>
>> (defvar fuzz-factor 1.0e-6)
>> (defun approx-equal (x y)
>> (or (and (= x 0) (= y 0))
>> (< (/ (abs (- x y))
>> (max (abs x) (abs y)))
>> fuzz-factor)))
>>
>> When either x or y is 0.0, but not both, this gives nil no matter how close
>> the other number is to zero. I think this is more like what is needed:
>>
>> (defun approx-equal (x y &optional fuzz)
>> (setq fuzz (or fuzz 1.0e-8))
>> (cond ((= x 0.0) (< y fuzz))
>> ((= y 0.0) (< x fuzz))
>> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
>
> The problem here is that fuzz is a _relative_ measure of equality, and
> you employ it as an absolute measure here. I don't think it a good
> idea at all that 1e-12 and 0.995e-12 are considered different, while
> 1e-8 and 0.0 are considered equal.
Agree!
And:
(approx-equal 0.0 -1.0e10) => t
--
Kim F. Storm <storm@cua.dk> http://www.cua.dk
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:42 ` Kim F. Storm
@ 2006-05-29 13:54 ` Lennart Borgman
2006-05-29 14:08 ` David Kastrup
0 siblings, 1 reply; 13+ messages in thread
From: Lennart Borgman @ 2006-05-29 13:54 UTC (permalink / raw
Cc: Drew Adams, Emacs-Devel
Kim F. Storm wrote:
> David Kastrup <dak@gnu.org> writes:
>
>
>> "Drew Adams" <drew.adams@oracle.com> writes:
>>
>>
>>> I blindly got bit by this one. The Elisp manual gives this as an example of
>>> how to test near equality of floating-point numbers:
>>>
>>> (defvar fuzz-factor 1.0e-6)
>>> (defun approx-equal (x y)
>>> (or (and (= x 0) (= y 0))
>>> (< (/ (abs (- x y))
>>> (max (abs x) (abs y)))
>>> fuzz-factor)))
>>>
>>> When either x or y is 0.0, but not both, this gives nil no matter how close
>>> the other number is to zero. I think this is more like what is needed:
>>>
>>> (defun approx-equal (x y &optional fuzz)
>>> (setq fuzz (or fuzz 1.0e-8))
>>> (cond ((= x 0.0) (< y fuzz))
>>> ((= y 0.0) (< x fuzz))
>>> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
>>>
>> The problem here is that fuzz is a _relative_ measure of equality, and
>> you employ it as an absolute measure here. I don't think it a good
>> idea at all that 1e-12 and 0.995e-12 are considered different, while
>> 1e-8 and 0.0 are considered equal.
>>
>
> Agree!
>
Hm. It is the relative distance from 0.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:54 ` Lennart Borgman
@ 2006-05-29 14:08 ` David Kastrup
2006-05-29 14:18 ` Lennart Borgman
0 siblings, 1 reply; 13+ messages in thread
From: David Kastrup @ 2006-05-29 14:08 UTC (permalink / raw
Cc: Emacs-Devel, Drew Adams, Kim F. Storm
Lennart Borgman <lennart.borgman.073@student.lu.se> writes:
> Kim F. Storm wrote:
>> David Kastrup <dak@gnu.org> writes:
>>
>>
>>> "Drew Adams" <drew.adams@oracle.com> writes:
>>>
>>>
>>>> I blindly got bit by this one. The Elisp manual gives this as an example of
>>>> how to test near equality of floating-point numbers:
>>>>
>>>> (defvar fuzz-factor 1.0e-6)
>>>> (defun approx-equal (x y)
>>>> (or (and (= x 0) (= y 0))
>>>> (< (/ (abs (- x y))
>>>> (max (abs x) (abs y)))
>>>> fuzz-factor)))
>>>>
>>>> When either x or y is 0.0, but not both, this gives nil no matter how close
>>>> the other number is to zero. I think this is more like what is needed:
>>>>
>>>> (defun approx-equal (x y &optional fuzz)
>>>> (setq fuzz (or fuzz 1.0e-8))
>>>> (cond ((= x 0.0) (< y fuzz))
>>>> ((= y 0.0) (< x fuzz))
>>>> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
>>>>
>>> The problem here is that fuzz is a _relative_ measure of equality, and
>>> you employ it as an absolute measure here. I don't think it a good
>>> idea at all that 1e-12 and 0.995e-12 are considered different, while
>>> 1e-8 and 0.0 are considered equal.
>>>
>>
>> Agree!
>>
> Hm. It is the relative distance from 0.
It is merely the distance from 0, not the "relative distance".
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 14:08 ` David Kastrup
@ 2006-05-29 14:18 ` Lennart Borgman
2006-05-29 14:23 ` David Kastrup
0 siblings, 1 reply; 13+ messages in thread
From: Lennart Borgman @ 2006-05-29 14:18 UTC (permalink / raw
Cc: Emacs-Devel, Drew Adams, Kim F. Storm
David Kastrup wrote:
>>>>>
>>>>>
>>>> The problem here is that fuzz is a _relative_ measure of equality, and
>>>> you employ it as an absolute measure here. I don't think it a good
>>>> idea at all that 1e-12 and 0.995e-12 are considered different, while
>>>> 1e-8 and 0.0 are considered equal.
>>>>
>>>>
>>> Agree!
>>>
>>>
>> Hm. It is the relative distance from 0.
>>
>
> It is merely the distance from 0, not the "relative distance".
>
Yes, in a sense you are right. I should have expressed my self a bit
differently, but I am afraid you missed the point. The crucial thing is
that you divide the difference with the "distance" from 0 to construct
the number you compare to the fuzz factor.
It seems reasonable to me but breaks down in the special case where one
of the numbers are 0 (and the other is not).
Or am I missing something?
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 14:18 ` Lennart Borgman
@ 2006-05-29 14:23 ` David Kastrup
2006-05-29 14:40 ` Lennart Borgman
0 siblings, 1 reply; 13+ messages in thread
From: David Kastrup @ 2006-05-29 14:23 UTC (permalink / raw
Cc: Emacs-Devel, Drew Adams, Kim F. Storm
Lennart Borgman <lennart.borgman.073@student.lu.se> writes:
> David Kastrup wrote:
>>>>>>
>>>>> The problem here is that fuzz is a _relative_ measure of equality, and
>>>>> you employ it as an absolute measure here. I don't think it a good
>>>>> idea at all that 1e-12 and 0.995e-12 are considered different, while
>>>>> 1e-8 and 0.0 are considered equal.
>>>>>
>>>> Agree!
>>>>
>>> Hm. It is the relative distance from 0.
>>>
>>
>> It is merely the distance from 0, not the "relative distance".
>>
> Yes, in a sense you are right. I should have expressed my self a bit
> differently, but I am afraid you missed the point. The crucial thing
> is that you divide the difference with the "distance" from 0 to
> construct the number you compare to the fuzz factor.
In which case, the relative distance from 0 is 1.0 for _any_ nonzero
number. And your point was?
> It seems reasonable to me but breaks down in the special case where
> one of the numbers are 0 (and the other is not).
Relative measures don't work when comparing with 0. But 0.0 can
pretty much only come about by cancellation, and then comparison is
unreliable anyway. It might be worth pointing out, but it certainly
is not a remedy to rechristen a relative measure to absolute.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 14:23 ` David Kastrup
@ 2006-05-29 14:40 ` Lennart Borgman
0 siblings, 0 replies; 13+ messages in thread
From: Lennart Borgman @ 2006-05-29 14:40 UTC (permalink / raw
Cc: Kim F. Storm, Drew Adams, Emacs-Devel
David Kastrup wrote:
>>>
>>>
>> Yes, in a sense you are right. I should have expressed my self a bit
>> differently, but I am afraid you missed the point. The crucial thing
>> is that you divide the difference with the "distance" from 0 to
>> construct the number you compare to the fuzz factor.
>>
>
> In which case, the relative distance from 0 is 1.0 for _any_ nonzero
> number. And your point was?
>
This of course.
>
>> It seems reasonable to me but breaks down in the special case where
>> one of the numbers are 0 (and the other is not).
>>
>
> Relative measures don't work when comparing with 0. But 0.0 can
> pretty much only come about by cancellation, and then comparison is
> unreliable anyway. It might be worth pointing out, but it certainly
> is not a remedy to rechristen a relative measure to absolute.
>
I guess that is true. So maybe it is better to ask Drew what he was
going to compare so we can construct a better measurement.
^ permalink raw reply [flat|nested] 13+ messages in thread
* RE: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:40 ` Lennart Borgman
@ 2006-05-29 18:14 ` Drew Adams
2006-05-30 3:46 ` Richard Stallman
0 siblings, 1 reply; 13+ messages in thread
From: Drew Adams @ 2006-05-29 18:14 UTC (permalink / raw
> (defun approx-equal (x y &optional fuzz)
> (setq fuzz (or fuzz 1.0e-8))
> (cond ((= x 0.0) (< y fuzz))
> ((= y 0.0) (< x fuzz))
> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
Leonard> Looks reasonable, but you have to use (< (abs y) fuzz) etc.
Right - forgot the abs. Thx.
David> The problem here is that fuzz is a _relative_ measure of
equality, and you employ it as an absolute measure here.
FUZZ is a relative measure in the final clause and an absolute measure in
the first two clauses. Anyway, you are right that my definition mixes
absolute with relative measures. It would also be right to say that the same
fuzz factor might not always be useful as both an absolute measure and a
relative measure this way.
My point was that the relative measure given is useless as a measure of
proximity to zero. Or, as you echoed it, "Relative measures don't work when
comparing with 0." The difference from zero compared to the maximum is
always exactly 1.0. By that relative measure, neither 1,000,000,000 nor
0.0000000001 is approximately zero - they fail equality to the same degree
(Animal Farm, revisited), as do all other floating-point numbers (except
0.0, which causes division by zero unless treated as a special case).
Neither absolute nor relative measure is appropriate in all cases - there is
no general comparison algorithm that is good all of the time (duh). Some
applications use absolute comparison (which has the drawback of being
relatively different comparing small numbers from comparing large numbers);
others use relative comparison (sacrificing approximate equality with zero);
still others use some combination of the two. And of course approximate
equality (by most definitions) is not transitive, whether measured
absolutely or relatively.
One article I came across put it this way: "Depending on how you came up
with the numbers, you may have 1.0 not being approximately equal to
0.999999, or you may have 1.0 being approximately equal to 0.0."
Here's a definition I came across that combines absolute and relative
comparisons in a way that is better than what I proposed. (I added the
defaults for the fuzz factors.)
(defun approx-equal (x y &optional rfuzz afuzz)
"Return non-nil if numbers X and Y are approximately equal.
RFUZZ is a relative fuzz factor. AFUZZ is an absolute fuzz factor.
RFUZZ defaults to 1.0e-8. AFUZZ defaults to (/ RFUZZ 10).
The algorithm is:
(< (abs (- X Y)) (+ AFUZZ (* RFUZZ (+ (abs X) (abs Y)))))."
(setq rfuzz (or rfuzz 1.0e-8) afuzz (or afuzz (/ rfuzz 10)))
(< (abs (- x y)) (+ afuzz (* rfuzz (+ (abs x) (abs y))))))
This is more flexible than both the definition I gave and the one in the
manual. You can of course still shoot yourself in the foot with this,
depending on the values you are testing and your choice of fuzz factors. In
my application this definition works well, as does the code I sent
originally: an absolute test against zero is in fact what I need.
Wrt the Elisp manual, I'd suggest 1) going with the original example, 2)
pointing out that it does not work for testing approximation to zero, and 3)
mentioning that an absolute test can sometimes be appropriate in that case.
FYI - These articles are interesting on testing floating-point approximate
equality: http://docs.sun.com/source/806-3568/ncg_goldberg.html,
http://www.visoracle.com/squeakfaq/float-precision.html. Knuth's Art of
Computer Programming vol 2 has a section on this which is also interesting.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:20 Elisp manual, node "Comparison of Numbers" Drew Adams
2006-05-29 13:33 ` David Kastrup
2006-05-29 13:40 ` Lennart Borgman
@ 2006-05-29 19:23 ` Stefan Monnier
2 siblings, 0 replies; 13+ messages in thread
From: Stefan Monnier @ 2006-05-29 19:23 UTC (permalink / raw
Cc: Emacs-Devel
> I blindly got bit by this one. The Elisp manual gives this as an example
> of how to test near equality of floating-point numbers:
> (defvar fuzz-factor 1.0e-6)
> (defun approx-equal (x y)
> (or (and (= x 0) (= y 0))
> (< (/ (abs (- x y))
> (max (abs x) (abs y)))
> fuzz-factor)))
> When either x or y is 0.0, but not both, this gives nil no matter how close
> the other number is to zero. I think this is more like what is needed:
> (defun approx-equal (x y &optional fuzz)
> (setq fuzz (or fuzz 1.0e-8))
> (cond ((= x 0.0) (< y fuzz))
> ((= y 0.0) (< x fuzz))
> (t (< (/ (abs (- x y)) (max (abs x) (abs y))) fuzz))))
There is no generally good solution to this problem. Depending on the
specific problem, one approach will work while that approach will fail
miserably in another context.
Welcome to the wonderful world of floating point and numerical analysis.
I don't think the Elisp manual should try to tackle these kinds of problems,
especially given how rarely floats are used in Emacs.
Stefan
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 13:33 ` David Kastrup
2006-05-29 13:42 ` Kim F. Storm
@ 2006-05-29 21:28 ` Richard Stallman
1 sibling, 0 replies; 13+ messages in thread
From: Richard Stallman @ 2006-05-29 21:28 UTC (permalink / raw
Cc: drew.adams, emacs-devel
The problem here is that fuzz is a _relative_ measure of equality, and
you employ it as an absolute measure here.
That is true -- but, in the case where one of the numbers is zero,
we have no way to apply a relative criterion to the other number.
There is no possible standard for it to be relative to.
Perhaps the idea of approximate equality can't be applied
to the case where either of the numbers is zero.
Perhaps it should always return nil in that case.
If so, the current definition is correct,
though not written very clearly for the result it gives.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Elisp manual, node "Comparison of Numbers"
2006-05-29 18:14 ` Drew Adams
@ 2006-05-30 3:46 ` Richard Stallman
0 siblings, 0 replies; 13+ messages in thread
From: Richard Stallman @ 2006-05-30 3:46 UTC (permalink / raw
Cc: emacs-devel
Here's a definition I came across that combines absolute and relative
comparisons in a way that is better than what I proposed. (I added the
defaults for the fuzz factors.)
(defun approx-equal (x y &optional rfuzz afuzz)
"Return non-nil if numbers X and Y are approximately equal.
RFUZZ is a relative fuzz factor. AFUZZ is an absolute fuzz factor.
RFUZZ defaults to 1.0e-8. AFUZZ defaults to (/ RFUZZ 10).
The algorithm is:
(< (abs (- X Y)) (+ AFUZZ (* RFUZZ (+ (abs X) (abs Y)))))."
(setq rfuzz (or rfuzz 1.0e-8) afuzz (or afuzz (/ rfuzz 10)))
(< (abs (- x y)) (+ afuzz (* rfuzz (+ (abs x) (abs y))))))
Since this is simple and clean, let's use it as the example.
Or else, let's simplify the example so it returns nil
directly when it sees 0 as an argument.
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2006-05-30 3:46 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2006-05-29 13:20 Elisp manual, node "Comparison of Numbers" Drew Adams
2006-05-29 13:33 ` David Kastrup
2006-05-29 13:42 ` Kim F. Storm
2006-05-29 13:54 ` Lennart Borgman
2006-05-29 14:08 ` David Kastrup
2006-05-29 14:18 ` Lennart Borgman
2006-05-29 14:23 ` David Kastrup
2006-05-29 14:40 ` Lennart Borgman
2006-05-29 21:28 ` Richard Stallman
2006-05-29 13:40 ` Lennart Borgman
2006-05-29 18:14 ` Drew Adams
2006-05-30 3:46 ` Richard Stallman
2006-05-29 19:23 ` Stefan Monnier
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).