www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Nice document on IEEE 754 floating point arithmetic

reply Norbert Nemec <Norbert Nemec-online.de> writes:
Hi there,

I just found a really nice document at:

 http://www.cs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF

It really gives a lot of insight on the rationale behind IEEE754 design,
also focusing a lot on language and compiler design.

One of the most relevant points with respect to D is probably the behavior
of comparison operators. The D specs go a rather practical way by defining
comparisons based on mathematical semantics. For floating points, though,
this is often not correct.

There probably are a few more points to consider when evaluating D for
numerical purposes. Some of the demands given in the document are probably
unrealistic for a general purpose language, but quite a number seem
perfectly reasonable to me.

Anyhow: instead of spending many words on the topic at this point, I would
rather advise anyone interested in numerics to have a look at the document
- be it only to get an understanding what the concerns might be about.

Ciao,
Norbert
Jan 10 2005
parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message
news:crv1i3$2bn0$1 digitaldaemon.com...
 Hi there,

 I just found a really nice document at:

  http://www.cs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF

 It really gives a lot of insight on the rationale behind IEEE754 design,
 also focusing a lot on language and compiler design.

 One of the most relevant points with respect to D is probably the behavior
 of comparison operators. The D specs go a rather practical way by defining
 comparisons based on mathematical semantics. For floating points, though,
 this is often not correct.

 There probably are a few more points to consider when evaluating D for
 numerical purposes. Some of the demands given in the document are probably
 unrealistic for a general purpose language, but quite a number seem
 perfectly reasonable to me.

 Anyhow: instead of spending many words on the topic at this point, I would
 rather advise anyone interested in numerics to have a look at the document
 - be it only to get an understanding what the concerns might be about.

Thanks for the pointer. As far as I know, D (and Digital Mars C/C++) are the only languages that properly support NaN's in comparison operators. This is deliberate on my part, even at the slight cost of performance it entails. Digital Mars compilers have always leaned towards doing accurate and correct floating point as a priority over performance.
Jan 12 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Walter wrote:
 As far as I know, D (and Digital Mars C/C++) are
 the only languages that properly support NaN's in comparison operators.
 This is deliberate on my part, even at the slight cost of performance it
 entails. Digital Mars compilers have always leaned towards doing accurate
 and correct floating point as a priority over performance.

Great" "Full IEEE 754 conformance" definitely would be a tremendous argument for using D in the numerics field. Anyhow, there is a few details I wonder about: A) The chapter "Expressions", section "Equality Expressions" states "If either or both operands are NaN, then both the == and != comparisons return false." which is in contrast to the table in "Relational Expressions" (and to the IEEE754 standard as well) B) The note 1. under the same table states that "For floating point comparison operators, (a !op b) is not the same as !(a op b)." It should be noted that this refers only to the question whether they signal on NaNs - otherwise, this sentence is hard to understand. C) Raising of Invalid Exceptions on should just be an option but not the default. IEEE754 states that a *flag* should be raised which can then be checked and reset by the user lateron. Raising an exception would be equivalent to what the document calls "trapping". Unless you are debugging your code, that is hardly ever what you want. The whole power of the NaN-concept is that they do not interrupt the calculation but instead are handled just like similar numbers. My output data from numerical calculations usually is a long block of floating points which may contain some NaNs. This simply tells me that I hit singularities or other special points in some cases and either drop or specially mark these points in the resulting plots. D) Furthermore: even if the behavior for native floats is correct, operator overloading still is not capable to mimic this behavior. In any case, I think that operator overloading is not quite flexible enough in several respects. Matlab, for example, allows comparing two arrays of numbers, returning an array of bools, which can then be used in many ways. In D, this would not be possible, since the comparison operators are based on opCmp. Furthermore, ! is not overloadable at all, so even if I write an opEquals for two arrays returning an array of bools, I could never mimic the correct behavior for != My suggestion would be: * Introduce opNot (unlike && and ||, there is no compelling reason why it should not be overloadable) * Introduce opLess, opGreater, opLessOrEqual, opGreaterOrEqual. If these are not defined, the compiler can still fall back to opCmp. In the same course, even == could fall back to opCmp if opEquals does not exist.
Jan 12 2005
next sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Norbert Nemec wrote:

 My suggestion would be:
 * Introduce opNot (unlike && and ||, there is no compelling reason why it
 should not be overloadable)
 * Introduce opLess, opGreater, opLessOrEqual, opGreaterOrEqual. If these
 are not defined, the compiler can still fall back to opCmp. In the same
 course, even == could fall back to opCmp if opEquals does not exist.

On second thought: if this were done, one clearly would have to take care of .sort and other builtins that are based on opCmp. How is .sort currently supposed to behave on hitting a NaN in an array of floats? One way to deal with this would be to offer both: opLess etc. for doing exact comparisons that may follow IEEE754 standards or whatever exactly, and opCmp that might not be mathematically correct but guarantees a partial ordering of the list. For float-like objects, opCmp would then just do binary sorting which is mostly accurate and good for sortings floats, but not IEEE754 conformant. Still, <, >, <=, etc. would do the correct thing since they are mapped to the opLess, etc. functions instead of the over-simplistic opCmp
Jan 13 2005
parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message
news:cs5bt7$1s3s$1 digitaldaemon.com...
 How is .sort currently supposed to behave on hitting a NaN in an array of
 floats?

Putting all the NaN's at the end is one reasonable solution.
 One way to deal with this would be to offer both: opLess etc. for doing
 exact comparisons that may follow IEEE754 standards or whatever exactly,
 and opCmp that might not be mathematically correct but guarantees a

 ordering of the list. For float-like objects, opCmp would then just do
 binary sorting which is mostly accurate and good for sortings floats, but
 not IEEE754 conformant. Still, <, >, <=, etc. would do the correct thing
 since they are mapped to the opLess, etc. functions instead of the
 over-simplistic opCmp

Jan 13 2005
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Walter wrote:
 "Norbert Nemec" <Norbert Nemec-online.de> wrote in message
 news:cs5bt7$1s3s$1 digitaldaemon.com...
 
How is .sort currently supposed to behave on hitting a NaN in an array of
floats?

Putting all the NaN's at the end is one reasonable solution.

I noticed in that document that the spec was designed such that you could sort floats using an ordinary sort (as though they were ints). I don't remember any exception for NaN's, but maybe I missed or forgot it.
Jan 13 2005
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Russ Lewis wrote:

 Walter wrote:
 "Norbert Nemec" <Norbert Nemec-online.de> wrote in message
 news:cs5bt7$1s3s$1 digitaldaemon.com...
 
How is .sort currently supposed to behave on hitting a NaN in an array of
floats?

Putting all the NaN's at the end is one reasonable solution.

I noticed in that document that the spec was designed such that you could sort floats using an ordinary sort (as though they were ints). I don't remember any exception for NaN's, but maybe I missed or forgot it.

True, if you sort floats by their binary representation, you get the correct ordering for all finite and infinite values with the NaNs sorted to some special position. This would mean that opCmp for floats could just do a binary comparison while the relational operators would have to be decoupled from it. Exactly following my proposal that relational operators should be overloadable individually (using opLess, opGreater, etc.) and only fall back to opCmp if the former do not exist.
Jan 13 2005
prev sibling parent "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert Nemec-online.de> wrote in message
news:cs41vr$2vgl$1 digitaldaemon.com...
 Walter wrote:
 As far as I know, D (and Digital Mars C/C++) are
 the only languages that properly support NaN's in comparison operators.
 This is deliberate on my part, even at the slight cost of performance it
 entails. Digital Mars compilers have always leaned towards doing


 and correct floating point as a priority over performance.

Great" "Full IEEE 754 conformance" definitely would be a tremendous

 for using D in the numerics field.

 Anyhow, there is a few details I wonder about:

 A) The chapter "Expressions", section "Equality Expressions" states

  "If either or both operands are NaN, then both the == and != comparisons
  return false."

 which is in contrast to the table in "Relational Expressions" (and to the
 IEEE754 standard as well)

I believe D has this to be correct. Note that there are two different equality operators, one that says a NaN operand returns false and the other giving true for a NaN operand. IEEE 754 suggests "=" for the former (lining up with D's "=="), and "?=" for the latter (in D it is "!<>").
 B) The note 1. under the same table states that "For floating point
 comparison operators, (a !op b) is not the same as !(a op b)." It should

 noted that this refers only to the question whether they signal on NaNs -
 otherwise, this sentence is hard to understand.

NaNs in general are hard to get used to <g>. But it's worthwhile.
 C) Raising of Invalid Exceptions on should just be an option but not the
 default. IEEE754 states that a *flag* should be raised which can then be
 checked and reset by the user lateron. Raising an exception would be
 equivalent to what the document calls "trapping". Unless you are debugging
 your code, that is hardly ever what you want. The whole power of the
 NaN-concept is that they do not interrupt the calculation but instead are
 handled just like similar numbers. My output data from numerical
 calculations usually is a long block of floating points which may contain
 some NaNs. This simply tells me that I hit singularities or other special
 points in some cases and either drop or specially mark these points in the
 resulting plots.

True, and this is exactly what D does - set the invalid operation flag, which is sticky, and can be tested/set/cleared under programmer control.
 D) Furthermore: even if the behavior for native floats is correct,

 overloading still is not capable to mimic this behavior.

 In any case, I think that operator overloading is not quite flexible

 in several respects. Matlab, for example, allows comparing two arrays of
 numbers, returning an array of bools, which can then be used in many ways.
 In D, this would not be possible, since the comparison operators are based
 on opCmp. Furthermore, ! is not overloadable at all, so even if I write an
 opEquals for two arrays returning an array of bools, I could never mimic
 the correct behavior for !=

 My suggestion would be:
 * Introduce opNot (unlike && and ||, there is no compelling reason why it
 should not be overloadable)
 * Introduce opLess, opGreater, opLessOrEqual, opGreaterOrEqual. If these

 not defined, the compiler can still fall back to opCmp. In the same

 even == could fall back to opCmp if opEquals does not exist.

You're right that the current opCmp overloading cannot handle NaN operands. Overloading opNot won't help, either, and I firmly believe that it is a mistake to overload opNot. The problem is that opCmp returns one of 3 states, but 4 states are needed. I think the correct approach is to have an opFCmp overload that returns one of 4 states (less than, greater than, equal, unordered) which the code generator can use to support each of the extended relational operators. The operator overloading mechanism would first look for opFCmp, only if that does not exist will it look for opCmp.
Jan 13 2005