On to Hydro

Karp, Alan alan_karp@hp.com
Tue, 22 Aug 2000 08:57:42 -0700


You can't fool Mother Nature or Father Kahan.  Floating point arithmetic is
not the same as real arithmetic, and you've got to be very careful about
getting a consistent set of rules.  That's why it took so long to develop
the standard.  Everyone who has violated the standard has gotten into
trouble at some point.  You may have a particularly clever solution for a
some problem, but I guarantee the definition is inconsistent with some other
calculation.  Instead of saying "Ugh", think of it as a legitimate cop out.
"Gee, I know it doesn't make sense, but it follows the standard."

As far as sorting goes, you're free to do anything you want with NaNs.  Put
them at the beginning, the end, or throw an exception; it doesn't matter as
long as you're consistent.  Consistency is the key.  IA-64 has MIN and MAX
operations.  What's MIN(a,b) where a, b, or both are NaNs?  We wrestled with
this point until we realized that we could just use the < operation and take
what it gave us; a<b is false if either or both is a NaN.  We realized that
MIN(a,b) != MIN(b,a) when NaNs are involved, but at least we had a
consistent definition.  Unfortunately, MIN(a,b) always returns the second
argument, even if only the first is a NaN, which differs from the behavior
of other floating point ops.  The compute types argued for the normal
behavior, but the hardware guys wanted to save a few gates, and they won.
Still, you can't go far wrong if all your ordering is done with the same
operation, say <.  (Don't start mucking around with identities like a<b is
the same as b>=a; they don't always work with NaNs.)

There were long discussions about -0.  I favored treating -0 as the limit of
approaching 0 from below, and I have a few cases where that makes sense.
Kahan, on the other hand, has many more cases where you want the opposite
behavior.  On balance, his cases are more common, and the efficiency of the
underlying calculation has more improvement.  That's why 0 == -0 returns
true.  

By the way, division by zero returns infinity, not NaN, unless you're
dividing 0 by 0.  That's why your continued fraction works.  Kahan has a
monograph showing many more examples.

_________________________
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: Norman Hardy [mailto:norm@netcom.com]
> Sent: Monday, August 21, 2000 7:38 PM
> To: Tyler Close; Mark S. Miller
> Cc: E Language Discussions
> Subject: RE: On to Hydro
> 
> 
> At 9:02 -0400 00/08/18, Tyler Close wrote:
> 
> >...
> 
> 
> >They do not denote the same real number. They are different
> >numbers. -0.0 < 0.0 should be true. This behaviour agrees with that
> >specified for Double.compareTo in the JDK1.3 documentation.
> 
> I don't know about IEEE floats but when it comes to reals 0 = -0.
> 
> All mathematicians agree that between any two distinct reals there 
> lies another real distinct from both. What is between 0 and -0 if 
> they are distinct?
> 
> Not that this bears on the decision at hand.
> 
> My two cents are that you should either conform slavishly to IEEE 
> (ugh) or provide a total ordering so that sorts work. (Actually you 
> could do both, perhaps even provide a function of two reals!)
> 
> I have seen just one real case where division by 0 fed meaningfully 
> into another calculation. That was in continued fraction expressions 
> such as a+1/(b+1/(c + ... )).
> Simple algebra replaces most divides by multiplies and the advantage 
> evaporates and the calculation runs faster.
> 
> The most exasperating benefit of NaNs is in vector hardware where 
> most values calculated at once are useful and you can't afford to 
> stop to fuss over the oddball.
> -- 
> Norman Hardy  <http://cap-lore.com/>
>