Proofs & code for perfect-rounding binary <-> decimal

[Tim Peters]

The proceedings of the ACM SIGPLAN '90 Conference on Programming
Language Design & Implementation (to be held June 20-22 in White
Plains NY) showed up yesterday as Volume 25 No 6 (June '90) of SIGPLAN
Notices.  Two papers are wonderfully relevant to the Conversion Wars:

   "How to Read Floating Point Numbers Accurately"
   William D Clinger (U of Oregon)
   pp 92-101

   "How to Print Floating-Point Numbers Accurately"
   Guy Steele (Thinking Machines)
   Jon L White (Lucid Inc)
   pp 112-126

There are no compromises with accuracy here (the algorithms do perfect
rounding in all cases), detailed proofs are included, and the authors
worry quite a bit about efficiency (although in the decimal->binary
case Clinger can't get away without needing arbitrary bignums in some
cases, and proves why he can't; the Clinger algorithms are also given
in Lisp, which is probably not *my* first choice as an implementation
language for such things <0.2 grin>).

The Steele/White paper also claims to solve a more interesting
problem, namely writing a given floating point number using the
*minimum* number of decimal digits that guarantees the Clinger
algorithm will reconstruct the Steel/White algorithm's input exactly
(e.g., printing out 1/2 as "0.5" instead of as "0.50000000000000000"
or some other equally user-unfriendly monster ... Fortran list-
directed I/O could put this to good use).

Assuming the proofs check out, I will of course withdraw all my "but
it isn't public art!" objections.  But I'm still not sure these things
can be made to run "acceptably fast" <grin> ...

sometimes-feeling-like-a-dinosaur-in-heat-ly y'rs  - tim