comments on Clinger and Steele/White papers

[Tim Peters]

>  [david hough]
>  Clinger's algorithms require extended precision in hardware in
>  order to attain fast average execution time.

Well, it helps, but I'd say "require" is too strong!  I.e., Bellerophon
makes no essential use of extended precision floats unless it needs them
(in the first two cases it's using extended only incidentally because
the powers of 10 happen to be stored in that format, and the only ep
operation it uses then is the trivial extended->non-extended exact
conversion to dump the excess 0 bits).  And when it does need extended
precision, the worst path through the code uses a grand total of four ep
operations (one int->ep, two ep multiplies (one of which could be
eliminated with a not-unreasonably-larger power-of-10 table, the other
of which could be eliminated with an astronomical table <grin>), and one
ep->non-ep conversion to get the final result).  Faking this less-than-
a-handful of ep operations with integer arithmetic is, I think, likely
much less expensive than, e.g., faking the multiple-precision integers
needed if you can't cut the input off after 17 (19 really, assuming
64-bit integers are easily doable) digits.  Really hard for me to
imagine something more efficient (so long as it avoids the failure
case).

One thing I don't understand about the Clinger algorithm (& I hasten to
add that Clinger didn't claim to address it -- not his fault!) is how to
extend it efficiently to set the inexact flag properly when it needs to
resort to extended precision and/or bignums.  I.e., it's content to fake
division by 10^e via multiplication by an approximation to 1./10^e, and
does it carefully enough so that the final answer is correct, but once
that approximation is thrown in (*must* be inexact since 1./10^e isn't
representable for any int e>0) I don't see a fast way to figure out
whether the result lost information.  David?  Anyone?

>  The most interesting sentence in the Steele/White paper is "A
>  portable and performance-tuned implementation in C is in progress".

Caught my eye too <grin>, but I couldn't figure out whether that
sentence was written circa "the late 1970's" (along with most of the
rest of the paper) or was added for publication now.  Anyone know?

>  ...
>  The complexity of Fortran 90 is on the user's side as well as the
>  implementers, but correctly-rounded base conversion is a lot simpler
>  to understand on the user side and only more trouble for an
>  implementer.

Let's agree to disagree on this one -- complexity is complexity to me,
regardless of which side of the fuzzy "implementor/user" fence it falls
on.  If it falls on the user's side, then as a user I don't want to deal
with it; if it falls on the implementor's side, then as a user I'd be a
fool to trust my vendor to do it all right <grin>.  You don't see it
that way; that's fine, we're not going to convert each other (at least
not on this point <smile>).

>  > [tim p]
>  > I hope that whatever NCEG does here it makes it very clear ...
>  [dgh]
>  Regardless of the clarity of 754 and 854, requiring correct rounding
>  simplifies the document and continues to satisfy 754 and 854.
>  Correct rounding of base conversion puts those operations on an equal
>  footing with all other 754 and 854 operations, namely that one
>  numerical value is to be converted to another, observing rounding
>  modes if inexact, and setting exception status and possibly trapping
>  on inexact, underflow, overflow, and invalid attempts.

With a little more practice I think we can achieve world-class status in
the art of talking entirely passed each other <grin>.  I.e., I'm griping
I don't know what "perfect rounding" *means* and you're still telling me
what a good thing it is <smile>.  Mr.  Killian approached this before, so
I'll try to build on that:

1) Is it OK by NCEG if, as Sun apparently does these days, the "perfect
   input" routine gives up on setting inexact correctly if faced with
   more than some 512 input digits?

2) Is it OK by NCEG if, as MIPS apparently does these days, the "perfect
   input" routine gives up on setting inexact correctly if faced with
   more than 17 input digits?

3) Is it OK by NCEG if the "perfect input" routine takes the 754/854-
   blessed option of flatly ignoring all input digits after the 17th?

4) Is it OK by NCEG if the "perfect output" routine (God only knows
   whether this is OK by 754/854, but it is apparently what MIPS does
   these days) unconditionally spits out 0's after the 17th digit when
   printing an IEEE double and told to print out more than 17 digits?

5) If, e.g., I read "0.1" in as an IEEE double and print it out to 17
   significant digits, do I have to produce the obnoxious

    0.10000000000000001

   as I read the 754 std requiring me to do, or can I instead print the
   friendlier (and in no way less portably defined, and also less than
   1/2 ulp away from the internal value)

    0.10000000000000000

   produced by the Steele/White algorithms?  I think they make an
   excellent point that it's downright misleading to print non-zero
   digits beyond the accuracy inherent in the input.  The latter
   printout is exactly -5.5511151231257827021181583404541015625e-18 away
   from the internal representation of 0.1, while the former is exactly
   4.4488848768742172978818416595458984375e-18 away, so I agree the 754
   printout is "closer" -- but in an esoterically useless sense.  Both
   printouts are less than 0.5*2^-56 off, and so faithfully represent
   the internal form of 0.1 to full machine accuracy.  As a user I'd
   much rather see the latter.

6) Question #5 probably rattles some cages 'cause 17 is a "magic number"
   in 754/854.  So let's boost it:  if the NCEG perfect printer is told
   to print (double) 0.1 to 40 digits, does it have to produce the
   getting-really-silly-now

         0.1000000000000000055511151231257827021182

   or can it do the Steele/White

         0.1000000000000000000000000000000000000000

   instead?  (Note for the unduly concerned:  I think it would be easy to
   modify the Steele/White algorithms to produce the unexpected-string-
   of-trailing-digits forms -- but I think too that the authors would
   hate to see it done).

My *primary* gripe here is, again, that I don't know how to answer these
questions based on what the NCEG draft currently says (although I bet I
can guess right on #5 <grin>).  The primary plea (not necessarily
directed at DGH!) is just that the NCEG draft make the answers clear
before I (the generic "I" standing for all oppressed implementors of the
world) have to implement it.

half-of-nothing-is-greater-than-nothing-of-half-ly y'rs  - tim

Tim Peters   Kendall Square Research Corp
timaksr.com,  ksr!timaharvard.harvard.edu