Elisp manual, node "Comparison of Numbers"

Elisp manual, node "Comparison of Numbers"

[Drew Adams]

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))))

Re: Elisp manual, node "Comparison of Numbers"

[David Kastrup]

"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

Re: Elisp manual, node "Comparison of Numbers"

[Lennart Borgman]

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.

Re: Elisp manual, node "Comparison of Numbers"

[Kim F. Storm]

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

Re: Elisp manual, node "Comparison of Numbers"

[Lennart Borgman]

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.

Re: Elisp manual, node "Comparison of Numbers"

[David Kastrup]

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

Re: Elisp manual, node "Comparison of Numbers"

[Lennart Borgman]

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?

Re: Elisp manual, node "Comparison of Numbers"

[David Kastrup]

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

Re: Elisp manual, node "Comparison of Numbers"

[Lennart Borgman]

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.

RE: Elisp manual, node "Comparison of Numbers"

[Drew Adams]

    >   (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.

Re: Elisp manual, node "Comparison of Numbers"

[Stefan Monnier]

> 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

Re: Elisp manual, node "Comparison of Numbers"

[Richard Stallman]

    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.

Re: Elisp manual, node "Comparison of Numbers"

[Richard Stallman]

    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.