Xref: utzoo comp.theory.dynamic-sys:189 sci.math:15794 sci.physics:17525
Path: utzoo!utgpu!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.203346.9770@jato.jpl.nasa.gov>
Date: 15 Mar 91 20:33:46 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> <1991Mar15.202738.9606@jato.jpl.nasa.gov>
Reply-To: vsnyder@jato.Jpl.Nasa.Gov (Van Snyder)
Organization: Jet Propulsion Laboratory, Pasadena, CA
Lines: 40

In article <1991Mar15.202738.9606@jato.jpl.nasa.gov> vsnyder@jato.Jpl.Nasa.Gov (Van Snyder) writes:
>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
 ^^^^^^^^^^^^^^^^^ <---  oops! "add one to"
>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


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