🚀 go-pugleaf

In article <HQweb.382949$2x.123651@rwcrnsc52.ops.asp.att.net>,
"Glen Herrmannsfeldt" <gah@ugcs.caltech.edu> writes:
|> 
|> I am not sure that I understand it so well, but I saw an explanation that to
|> get proper rounding for division with an N bit quotient, it is necessary to
|> calculate 2N quotient bits.    I believe that this is related to the
|> statement about double rounding, where rounding to >=2N bits, and then
|> subsequently to N bits gets the same result as rounding directly to N bits.
|> Intermediate rounding to <2N bits before rounding to N bits can give the
|> wrong answer.

Yes, roughly, though it isn't so simple.  But the latter statements
are definitely correct.

|> The statement about division is in the IBM Systems Journal article on
|> extended precision floating point, and the DXR simulation routine.

It predates that, and is well-known.


The rough summary is that addition, subtraction, comparison and so
on need only a fixed number of extra bits to support any sane form
of rounding, where the number is typically 1 or 2 on top of the
guard bits.

Multiplication is a real pain, because it really needs to be done
to a full NxN -> 2N form, and THEN rounded.  There are optimisations,
of course.

Division is definitely tricky, because it depends on how you do it.
I don't know the methods used in hardware, but the various forms of
repeated subtraction mean that you need calculate only N bits, but
need to do that to 2N precision.  Newton-Raphson is similar.

It is fairly easy to prove that the issues are close to fundamental,
and that ANY accurate multiplication or division method will need
the extra precision.  A long time back (1980s?), R.P. Brent did a
PROPER complexity analysis of the basic operations, and showed why
multiplication was more complex than addition.  Division is well
known to be a simple factor of about 2-3 more expensive than
multiplication, of course, for large numbers of bits.

None of this changes when considering probabilistic versus
deterministic rounding.


Regards,
Nick Maclaren.