🚀 go-pugleaf

In article <1991Mar14.113902.97@bsu-ucs.uucp>
	00lhramer@bsu-ucs.uucp (Leslie Ramer) writes:
>I would much rather use Newton's method to find the square root or any other
>root for that matter. [...]
>
>Now the only problem is a starting value.  A decent starting value is 1.
>
At least for square and cube roots, there are good rational approximations
for starting values in "Computer Approximations" by Hart et. al.  The usual
practice in a library code for a typical (base 2) computer is to separate
the exponent and fraction of the floating point number.  Then (for square
roots), if the exponent is odd, divide the fraction by 2 (shift right one) and
subtract one from the exponent.  The square root is then the number whose
floating point representation has 1/2 the exponent as revised above, and a
fraction given by the square root of the input fraction as revised above.
Since the revised fraction, however, is between 1/4 and 1, however, it's
possible to get a reasonably close initial estimate from a rational approx-
imation.  Since Newton's method doubles the number of correct digits on each
iteration (when it's converging), getting 8 bits from the initial approximation
and then doing two iterations of Newton's method is adequate.

But the one-bit-at-a time algorithms that are similar to division algorithms
(but a little simpler) are what are used inside co-processor chips:  You
get a square root for the cost of one division (approximately), instead of 3
divisions, some multiplications, some adds (all floating point), and some
jerking around of the floating point representation.


-- 
vsnyder@jato.Jpl.Nasa.Gov
ames!elroy!jato!vsnyder
vsnyder@jato.uucp