correctly-rounded IEEE division/sqrt

[David G Hough at validgh]

Stuart Oberman posted the following interesting information to
comp.arch.arithmetic:

From: Stuart Oberman <stuart.obermanaamd.com>
Subject: Re: division and sqrt
Date: Tue, 24 Mar 1998 10:01:30 -0800
Xref: uunet comp.arch.arithmetic:3914

James Stine wrote:
> 
> Hi,
> 
> Does anybody know any good reference on IEEE 754 rounding in division
> and square root?  Thanks!
> 
> james stine
> jes6alehigh.edu


I thought I would take a shot at this, since division and square root
are subjects that I have dealt with a bit recently.

Last bit accuracy for division and square root is an ongoing challenge. 
Actually achieving an exactly-rounded result is not difficult; achieving
it quickly is the challenge. The degree of difficulty depends upon the
chosen division / square root algorithm. 

When using non-restoring, linear-converging algorithms such as the
classical
SRT forms, exact-rounding for IEEE-754 is straightforward. Specifically,
for
computing an n-bit quotient mantissa, it is sufficient to compute n+2
bits 
of quotient; 1 extra bit for a guard bit, and 1 extra bit due to
possible 
normalization. Since the input operands are assumed to be normalized
to the range of [1,2), the output quotient can be in the rage (0.5,2). 
Sticky bit generation is then simply a function of whether the remainder
is non-zero.

A good reference for exactly-rounded quotients / square roots using SRT
is obviously Profs. Ercegovac and Lang's book: Division and Square Root:
Digit Recurrence Algorithms and Implementations. Try chapter 6 for their
work on on-the-fly rounding / conversion.

As to rounding when using a functional iteration - based algorithm, the
difficulty is greater. The problem here of course is that although a 
quotient is approximated by iterations, little is known about the 
remainder, which is required by the IEEE 754 to get the sticky bit
right,
useful for rounding and potentially signalling an inexact exception. 
I have not found a widely available textbook which covers this subject.
One
possibility is to look at my coverage of the subject in my PhD thesis
of yesteryear, available at:

ftp://umunhum.stanford.edu/tr/oberman.nov96.thesis.ps.Z

Chapter 7 deals with techniques for fast rounding for functional
iteration-
based division algorithms. Square root techniques follow directly.
References
to other papers on the subject are included therein.

I hope this is of some assistance.

- Stuart Oberman
  stuart.obermanaamd.com