accuracy of inputs

[Jon L White]

re: Since we must nevertheless design general purpose libraries,
    the following rule of thumb may be used: make the function
    or operation (like +, sqrt, sin ...) as accurate as possible,
    assuming the input is exact, provided not "too much" performance
    is sacrificed. Manufacturers adopting IEEE 754 or 854 have

Nearly 18 years ago, I ran into one more face of this problem -- namely, 
that of read/print accuracy.  This means that the base-10 scientific
notation printout of a floating point number should be such that reading 
it back in produces *exactly* the same bitwise representation for the number. 

I tweaked around with various algorithms for printing PDP-10 format
numbers (conversion from radix-2 FP to radix 10 "E" format); Guy Steele 
and I tried to formalize these algorithms, but the actual appearance of 
a paper describing them was delayed until last June's SIGPLAN conference 
in White Plains, NY.  By that time, Will Clinger had written up a paper 
on the related, parallel problem of reading (base 10 to FP conversion).

Our contentions are that although one expects errors to be introduced by 
numerical algorithms, as well as by floating-point arithmetic (rounding),
there is no excuse for introducing them during the data-transmission
process.

The interesting thing is that for most of the 1970's, I couldn't get
anyone to take us seriously.  Here's a typical scenario, related to
the "straw man" you invoke:

   (1) Floating point numbers are inherently inaccurate, or are used 
       for inaccurate numerical approximations, so you are wasting your
       time by worring about the LSB during READ/PRINT.

   (2) "My own" version of printout is fully accurate because of 
        blah,blah,blah, . . .  After we produce a test case that
        shows that the alleged printer is in fact producing a result
        which is closer to a *different* representable number than
        the one started with, then the respondent begins to blame
        other factors (such as an error in the FP hardware!)

Seldom did I meet someone in the 1970's who understood that using
double-precision arithmetic with guard digits was not satisfactory
for printing double-precision numbers.  On the IBM/370 in fact, the
error is not restricted to one LSB, but would often creep up into
the next couple of bits (because the 370, by some stroke of genius,
used radix 16 rather than radix 2 . ..).

By the early 1980's, I had met not a few persons who believed that you 
simply needed n extra digits (bits) in order to do the base conversion.
Experimental evidence seemed to verify this when care was taken using
double-precision numbers during the intermediate calculations for printing
out single-precision formats.  But as you point out, it isn't so easy
to go to quad format when you want to print out double-precison forms.

Sometime in the late 1970's, I had a chance to talk about these ideas 
with Welvel Kahan at Berkeley; I asked him if he could show me a "closed
form" for the relation between the significand and exponent sizes and
the amount of extra precision required.  He conjectured that there was 
no simple, mathematical formula for this.  Since every implementation
of the IEEE standard will have only a finite number of representable
numbers, then in theory you could just find out the answer by exhaustion.
I think I did so for the PDP10 format (23-bit significand, but not IEEE 
format), but don't recall the sharp result; it was either 6 or 7 or 8 
extra bits needed.


The algorithm for reading floating-piont numbers in Lucid Common Lisp
uses some fail-safe heuristics to do quick-but-accurate conversion.
The fall-back uses "bignums", which for large exponents can be very
time consuming.  The heuristic, of course, isn't sharp, so there are
times when the fall-back must be used even though the "quick" method
was accurate.  If I really knew a good lower bound for the amount
of extra precision required, then it *might* be profitable to use
double-word or triple-word optimized bignums, rather than the actual 
arbitrary-precision of bignums.



-- JonL --


P.S. When I speak of the community of persons I met during these years,
     be aware that I had only tangential contact with real numerical 
     analysts.  My world was primarily computer languages, operating 
     systems, and artificial intelligence.