Comparing doubles

Comparing doubles

[Lars Brinkhoff]

Does the C standard define exactly how floating-point comparisons
should work?  Sections 6.5.8 Relational operators and 6.5.9 Equality
operators in C99 doesn't spell out any details.

In particular, would it be acceptable for a GCC back end to compare
two doubles by subtracting them, converting the result to float, and
then compare the result against zero?

Re: Comparing doubles

[Geoff Keating]

Lars Brinkhoff <lars@nocrew.org> writes:

> Does the C standard define exactly how floating-point comparisons
> should work? 

No, it doesn't.  Most of the specification is in appendix F, but that
appendix is optional.

> Sections 6.5.8 Relational operators and 6.5.9 Equality
> operators in C99 doesn't spell out any details.
> 
> In particular, would it be acceptable for a GCC back end to compare
> two doubles by subtracting them, converting the result to float, and
> then compare the result against zero?

If you define __STDC_IEC_559__, no.  Otherwise, you can do whatever
you like, although it might give a less-than-useful FP implementation.

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>

Re: Comparing doubles

[Lars Brinkhoff]

> Lars Brinkhoff <lars@nocrew.org> writes:
> > would it be acceptable for a GCC back end to compare two doubles
> > by subtracting them, converting the result to float, and then
> > compare the result against zero?

Geoff Keating <geoffk@geoffk.org> writes:
> If you define __STDC_IEC_559__, no.

That is now the case.

> Otherwise, you can do whatever you like, although it might give a
> less-than-useful FP implementation.

Alan Lehotsky <apl@alum.mit.edu> writes:
> I don't quite remember what PDP10 doubles were like, but if you
> don't have NANs, then using subtraction is probably a viable
> approach.

PDP-10 doubles are just floats with one more word of mantissa.  There
are no NANs (nor infinities or -0).  Floating-point numbers have the
property that (when normalized) they can be compared using the normal
integer-comparing instructions.

> The problem with using subtract is that you may [...] have an
> undetected underflow interpreted as equality when it isn't.

That is understood.

Mark Hahn <hahn@physics.mcmaster.ca> writes:
> calling the inputs "double" would seem extremely dishonest then...

Somewhat devious, yes, but not extremely dishonest, really?

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

Re: Comparing doubles

[Lars Brinkhoff]

Lars Brinkhoff <lars.spam@nocrew.org> writes:
> > Lars Brinkhoff <lars@nocrew.org> writes:
> > > would it be acceptable for a GCC back end to compare two doubles
> > > by subtracting them, converting the result to float, and then
> > > compare the result against zero?
> Geoff Keating <geoffk@geoffk.org> writes:
> > If you define __STDC_IEC_559__, no.
> That is now the case.

Sorry, NOT the case.

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

Re: Comparing doubles

[Tim Hollebeek]

On Mon, Jul 01, 2002 at 08:15:54PM +0200, Lars Brinkhoff wrote:
> 
> In particular, would it be acceptable for a GCC back end to compare
> two doubles by subtracting them, converting the result to float, and
> then compare the result against zero?

Think very very hard before throwing away the transitive property of
equality.

Re: Comparing doubles

[Alan Lehotsky]

At 8:15 PM +0200 7/1/02, Lars Brinkhoff wrote:
>Does the C standard define exactly how floating-point comparisons
>should work?  Sections 6.5.8 Relational operators and 6.5.9 Equality
>operators in C99 doesn't spell out any details.
>
>In particular, would it be acceptable for a GCC back end to compare
>two doubles by subtracting them, converting the result to float, and
>then compare the result against zero?

I don't quite remember what PDP10 doubles were like, but if you don't 
have NANs, then using subtraction is probably a viable approach.  You 
might look at how this is implemented in the softfloat libraries.  It 
is probably  reasonable to check the signs, check the exponents and 
then as a last resort check the magnitudes.  The problem with using 
subtract is that you may trigger underflow exceptions or have an 
undetected underflow interpreted as equality when it isn't.

If you can run paranoia successfully, you probably have dealt with 
the whole class of comparison problems that are possible....

-- Al

-- 
		    Quality Software Management
		http://home.earthlink.net/~qsmgmt
		          apl@alum.mit.edu
		          (978)287-0435 Voice
		          (978)808-6836 Cell

	Software Process Improvement / Management Consulting
	     Language Design / Compiler Implementation

Re: Comparing doubles

[Robert Dewar]

> In particular, would it be acceptable for a GCC back end to compare
> two doubles by subtracting them, converting the result to float, and
> then compare the result against zero?

no, this is not even approximately correct

Re: Comparing doubles

[Robert Dewar]

> If you define __STDC_IEC_559__, no.  Otherwise, you can do whatever
> you like, although it might give a less-than-useful FP implementation.

Well by this viewpoint, you can implement addition by doing a subtraction.
Although a fully formal view of the standard might be consistent with this
approach, in practice we expect + to do an addition, and we expect equality
to do an equality operation, both in the usually understood informal meanings
of the terms, i.e. + translates to a floating-point add, and = translates
to a floating-point equals. Doing floating-point equality by subtraction
and test for zero is just too far from this expectation on any modern
machine.

Re: Comparing doubles

[Paul Koning]

Excerpt of message (sent 6 July 2002) by Robert Dewar:
> > If you define __STDC_IEC_559__, no.  Otherwise, you can do whatever
> > you like, although it might give a less-than-useful FP implementation.
> 
> Well by this viewpoint, you can implement addition by doing a subtraction.
> Although a fully formal view of the standard might be consistent with this
> approach, in practice we expect + to do an addition, and we expect equality
> to do an equality operation, both in the usually understood informal meanings
> of the terms, i.e. + translates to a floating-point add, and = translates
> to a floating-point equals. Doing floating-point equality by subtraction
> and test for zero is just too far from this expectation on any modern
> machine.

I don't think Lars was talking about a modern machine... :-)

In any case, I don't understand these points.  Certainly not the one
about subtraction.  The only reasonable expectation is that the
implementation should produce results that conform to the standard to
which it is implemented.  Whether addition is done by complement
followed by subtract, or subtract is done by complement and add, or
neither is true, is irrelevant so long as the answer is right.

Given that floating point negate can always be done exactly, I don't
see any reason why an implementation couldn't map subtract into add or
vice versa.

As for compare, I don't claim to know the intricacies of IEEE NaN and
all that, but surely on older float formats at least, compare is
indeed internally just a subtract and test for zero?  Or a normalize
(if applicable) and bitwise compare?  (The latter is definitely the
case on the CDC 6600, to use an old example.)

     paul

Re: Comparing doubles

[Tim Hollebeek]

On Sun, Jul 07, 2002 at 09:09:45AM -0400, Paul Koning wrote:
> 
> As for compare, I don't claim to know the intricacies of IEEE NaN and
> all that, but surely on older float formats at least, compare is
> indeed internally just a subtract and test for zero?

The original suggestion, which seems to be missed by many, was
subtract _doubles_ and compare to _float_ zero.  Assuming that wasn't
an mistake, it is far, far different from standard equality (due to
the loss of precision from truncation).

Truncation before compare allows {a==b, b==c, c!=a}, and all other
sorts of unreasonable things.  Regardless of whether the standard
strictly requires it or not, it is reasonable to expect equality to be
an equivalence operation.

-Tim

Re: Comparing doubles

[Lars Brinkhoff]

Tim Hollebeek <tim@hollebeek.com> writes:
> On Sun, Jul 07, 2002 at 09:09:45AM -0400, Paul Koning wrote:
> > As for compare, I don't claim to know the intricacies of IEEE NaN and
> > all that, but surely on older float formats at least, compare is
> > indeed internally just a subtract and test for zero?
> The original suggestion, which seems to be missed by many, was
> subtract _doubles_ and compare to _float_ zero.

Yes.

Some more information about the floating-point format (not IEEE) in
question: there are no NaNs, infinities, or -0.  FLT_MIN ==
(float)DBL_MIN.  The double format is just a float number with an
extra word of mantissa.

I think this means that the proposed operation (subtraction followed
by truncation and comparison against zero) will only fail if there is
an operand that is too small to be normalized.

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

Re: Comparing doubles

[Robert Dewar]

<<In any case, I don't understand these points.  Certainly not the one
about subtraction.  The only reasonable expectation is that the
implementation should produce results that conform to the standard to
which it is implemented.  Whether addition is done by complement
followed by subtract, or subtract is done by complement and add, or
neither is true, is irrelevant so long as the answer is right.
>>

YOu missed my point.

First, what do we mean by "answer is right". Well the standard does not
define this. At one level, doing addition by complement followed by
subtract is obviously wrong since it does not give proper IEEE minus
zero semantics. At the other end, doing a subtraction *instead* of
an addition (which is what I was referring to) gives obviously drastically
wrong results. But the standard has little to say about what is right or
wrong, so we really can't turn to the standard in judging what is 
reasonably conformant in this respect.

In the case of equality, it is reasonable to think that 

a) you should be able to compare any valid fpt numbers
b) you should get true if and only if the numbers are the same

doing comparisons by subtraction violates both these expectations, so
at least on a machine where it is reasonably possible to do a) and b)
then any compiler which does not do a) and b) is in my view an incorrect
implementation.

Note that it is often possible to do floating-point comparisons in the
informal sense of a) and b) with integer comparison operations.
(the only glitch being signed zeros)

Re: Comparing doubles

[Kai Henningsen]

dewar@gnat.com (Robert Dewar)  wrote on 07.07.02 in <20020707145355.AFF58F28D5@nile.gnat.com>:

> First, what do we mean by "answer is right". Well the standard does not
> define this. At one level, doing addition by complement followed by
> subtract is obviously wrong since it does not give proper IEEE minus
> zero semantics. At the other end, doing a subtraction *instead* of

That is "obvious" only if you have reason to expect IEEE minus zero  
semantics, which in a non-IEEE reals implementation you most certainly  
don't. Many of those don't even *have* the concept of "negative zero".

Your whole argument seems to be based on IEEE reals. Fine if that's what  
they're supposed to be, worthless otherwise.

If your reals do not have IEEE-style NaN or signed zero or stuff like  
that, I still see two problems with the proposed scheme.

Buut first, just to be clear what we are talking about, here is how I  
understand that scheme:

int double_equal(double a, double b)
{
        double c = a - b;     /*1*/
        float d = (float)c;   /*2*/
        return d == 0.0;      /*3*/
}

Line 1 has the problem that you can have an overflow. I.e., depending on  
the actual values of a and b, the result can be too large to be presented  
in a double. *If* you can catch that case and convert it to a "return 0",  
fine, otherwise you have a problem.

That subtraction can also underflow, if both a and b are already close to  
zero. If you have un-normalized doubles, you can still represent the  
result; if not, given that you are about to convert it into a float which  
certainly will not be able to represent a number that double can't, this  
means according to the proposed algorithm you should consider this case as  
"equal". The same comments about handling it apply as in the overflow  
case.

Line 2 obviously can again produce over- or underflow the same as line 1,  
with all the same arguments.

In any case, by the time you reach line 3, you have lost some bits from  
the result of the subtraction. If you do not have any under- or overflow,  
given that you are doing nothing more than check if you have zero, that is  
harmless.

So, the problematic cases are those where you will produce either overflow  
or underflow, either in the subtraction or in the truncate. Otherwise, the  
loss of precision does not seem problematic (or in other words, the result  
seems to be exact in the cases where it works at all).

MfG Kai

Re: Comparing doubles

[Robert Dewar]

<<As for compare, I don't claim to know the intricacies of IEEE NaN and
all that, but surely on older float formats at least, compare is
indeed internally just a subtract and test for zero?  Or a normalize
(if applicable) and bitwise compare?  (The latter is definitely the
case on the CDC 6600, to use an old example.)
>>

No, because a subtract and test for zero is subject to problems with both
underflow and overflow and can therefore result in considering unequal
numbers to be equal.

Re: Comparing doubles

[Robert Dewar]

<<Truncation before compare allows {a==b, b==c, c!=a}, and all other
sorts of unreasonable things.  Regardless of whether the standard
strictly requires it or not, it is reasonable to expect equality to be
an equivalence operation.
>>

But it is not necessarily the case that a==a (in the case of a NaN) so
your equivalence relation does not cover NaN's. That's still reasonable,
but it is worth noticing the exception.

Re: Comparing doubles

[Tim Hollebeek]

> <<Truncation before compare allows {a==b, b==c, c!=a}, and all other
> sorts of unreasonable things.  Regardless of whether the standard
> strictly requires it or not, it is reasonable to expect equality to be
> an equivalence operation.
> >>
> 
> But it is not necessarily the case that a==a (in the case of a NaN) so
> your equivalence relation does not cover NaN's. That's still reasonable,
> but it is worth noticing the exception.

I was going to mention it, but couldn't find a good way of saying
"when restricted to 'real' values."  Thanks.