On to Hydro

[Karp, Alan]

I know I'm supposed to be lurking so I can do the work I'm being paid to do,
but I can't resist.  I was one of the designers of the IA-64 floating point
architecture, so I was forced to learn a good bit about the IEEE floating
point standard.  (And now a word from our sponsor: I believe the IA-64
floating point implementation is the only one that fully implements the
standard when speculative execution is used.) 

Tyler's definition of compare violates the standard.  I quote from Section
5.6 Comparison.  (I can't locate my version of the final standard, so my
information comes from "A Proposed Standard for Binary Floating-Point
Arithmetic", IEEE Press, 1981.)

	'every NaN shall compare "unordered" with everything, including
itself.'

In that same paragraph, the standard states

	'Comparisons shall ignore the sign of infinity in the projective
mode (where +inf = -inf), 
	and shall ignore the sign of zero (so +0 = -0).'

As far as exceptions go, the standard defines signaling and nonsignaling
NaN.  The former generates an exception any time it is used in a floating
point operation; the latter does not.

The standard also defines a "sticky bit" for each of the exceptions Invalid
Operation, Division by Zero, Overflow, Underflow, and Inexact.  These bits,
along with infinity arithmetic and NaNs, are extremely useful for improving
the performance of real codes.  Consider computing the norm of a vector, 

	s = 0
	for i = 1, n
	   s = s + v[i]*2
	twonorm = sqrt(s)


Look at all the things that can go wrong.  The sum could underflow or
overflow; one of the inputs could be a NaN or an infinity.  Without the full
standard, I'd need a separate pass through the array to test for all these
cases.  With the standard, I can clear the bits, run the loop, then check
the sticky bits.  Real codes run 20-200% faster, depending on the degree of
checking, because of this feature.

The bottom line is that this standard was designed by people smarter than
you or I (mostly Kahan, who is smarter than all of us put together).  There
are excellent reasons for its features.  Deviate from the standard at your
own risk.  

The easiest way to stick to the standard is to use the floating point ops on
your underlying chip.  Essentially all processors implement the standard,
and violations are considered errors to be fixed.

_________________________
Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278


> -----Original Message-----
> From: Tyler Close [mailto:tjclose@yahoo.com]
> Sent: Thursday, August 17, 2000 4:50 AM
> To: Mark S. Miller
> Cc: E Language Discussions
> Subject: RE: On to Hydro
> 
> 
> Markm wrote:
> > Unless anyone has a good objection, the next release of E
> > will continue to
> > use the current collection library by default, but will
> > also experimentally
> > include the 1.0 version of Hydro, so we can start playing
> > around with it.
> 
> I object. ;) I think you mean the 2.0 version of Hydro. 2.0 is the one
> that has the immutable containers. The 1.0 version uses mutable
> containers.
> 
> > Since Tyler & I both have strong styles, and since these styles are
> > different, it'll be interesting seeing what kinds of
> > conflicts we have.
> > Here's the first one I saw:
> >
> >
> > The contract for Comparison states that it provides a total
> > order, but the
> > implementation of GreaterDouble (an implementation of
> > Comparison) says:
> >
> >      /**
> >       * Compares the values of two <code>Double</code> objects.
> >       * @return  <code>true</code> if the first <code>Double</code>
> >       *          has a greater value.
> >       */
> >      public static
> >      boolean compare(Double a, Double b)
> >      {
> >          return a.doubleValue() > b.doubleValue();
> >      }
> >
> > In Java and IEEE, ">" is not a total ordering on floating
> > point values.
> > Rather,
> >
> >      anything < NaN   yields false
> >
> > and
> >
> >      anything > NaN   yields false
> 
> This is not a style conflict, it's a bug. I've corrected it (and a
> couple others) and posted a new version (Beta2) on my web site at:
> http://www.waterken.com/Hydro/2.0/
> 
> The new implementation of GreaterDouble is:
> 
> public static
> boolean compare(Double a, Double b)
> {
>     return a.doubleValue() > b.doubleValue() || (a.isNaN() &&
> !b.isNaN());
> }
> 
> I specified total ordering because I think most programmers are not
> prepared to deal with the subtleties between equivalence and equality.
> One example of this is a SortedSet of doubles with NaN. If two sets
> contain the same elements, you'd expect them to be equal, but they may
> not be, depending on when the NaN was inserted. This is just too
> surprising.
> 
> > Another is "<" for strict subset.
> 
> Could you explain this more.
> 
> Tyler
> 
> 
> _________________________________________________________
> Do You Yahoo!?
> Get your free @yahoo.com address at http://mail.yahoo.com
>