Xref: utzoo comp.theory.dynamic-sys:188 sci.math:15793 sci.physics:17524
Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!jato!vsnyder
From: vsnyder@jato.jpl.nasa.gov (Van Snyder)
Newsgroups: comp.theory.dynamic-sys,sci.math,sci.physics
Subject: Re: square roots by hand or computer
Message-ID: <1991Mar15.202738.9606@jato.jpl.nasa.gov>
Date: 15 Mar 91 20:27:38 GMT
References: <1991Feb28.220523.6184@zaphod.mps.ohio-state.edu> <1991Mar1.001103.6341@cec1.wustl.edu> <1991Mar14.113902.97@bsu-ucs.uucp> <1991Mar15.063023.6605@dsd.es.com>
Reply-To: vsnyder@jato.Jpl.Nasa.Gov (Van Snyder)
Organization: Jet Propulsion Laboratory, Pasadena, CA
Lines: 32

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