efficient base conversion algorithms

[David G. Hough on validgh]

The correctly-rounded base conversion algorithms implemented in SunOS 4.0
are characterized by using as high a precision integer arithmetic as
necessary to guarantee correct rounding.  As Tim's examples demonstrate,
sometimes that's pretty high.  But those cases are rare.

The principal inefficiency in SunOS 4.0 algorithms is the time required to
compute powers of 10**4 in base 2**16, or vice versa, for large powers.

SunOS 4.1 algorithms reduced the worst case time substantially by using
large tables of powers of ten.  Staticly linked executables were much
larger, of course.

C 1.0/Fortran 1.3.1, the current unbundled compiler products, and
the forthcoming C 1.1/Fortran 1.4 take things further by exploiting 
floating-point arithmetic to convert the common easy cases quickly.
The overall approach could be called RISCY: compute the common cases
quickly, fall back to slower methods when necessary.  Correctly-rounded
elementary transcendental functions would necessarily work the same way.

In general, getting correctly-rounded base conversion, or getting fast
almost-correctly-rounded base conversion, is not difficult; Coonen published
methods in his thesis 7 years ago.  Fast correctly-rounded is only 
difficult because the algorithms are more complicated.  It's been one of
my back-burner goals to put the algorithms from C 1.1/Fortran 1.4 into
a form suitable for public distribution, but I'm not making exciting progress.
A necessary first step is to provide the test programs necessary to evaluate
base-conversion algorithms.  Vern Paxson, who's on this mailing list, is
working on that problem, using some stuff I developed at Sun, augmented by
his own insights and some of the discussion from numeric-interest.