Newton-Raphson algorithm

[Dennis Brzezinski]

Earl Killian writes:
I am looking for references to Newton-Raphson algorithms for divide
and square root.  I know that it is difficult (but possible, as TI/Sun
proved) to get a correctly rounded result when you round at each
intermediate step, but I've heard that if you have a double-width
datapath available (e.g. on a machine with a fused multiply/add
instruction like the RS6000), that it is fairly easy.  If you can
provide any references for the latter approach, I would appreciate it.

Earl,
 There is a wealth of information on Newton-Raphson in the literature, but
for your specific request...IEEE exact divide/sqrt on a fused multiply-add
unit you should read Peter Markstein's paper " Computation of Elementary
Functions on the IBM RISC System/6000 Processor" pp 111-119, IBM Journal of
Research and Developoment, Vol.34, Number 1, January 1990.  The entire issue
is devoted to the first RS6000 product VLSI.  

You may also want to review the Goldschimt algorithm (Hennesy/Patterson 
Qualative Approach to Computer Architecture and the TI reference in that
book) as the latest IBM POWER2 has switched over. Gold..  offers more 
potential parallelism but does not guarantee convergence(i.e. may need a 
test for a fix-up).  Perhaps n-way superscalars can find some additional
advantages with Gold..


Regards,
Dennis Brzezinski
HP Labs Palo Alto
Personal Posting