Xref: utzoo comp.theory.dynamic-sys:184 sci.math:15777 sci.physics:17500
Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!news.cs.indiana.edu!bsu-cs!bsu-ucs.uucp!00lhramer
From: 00lhramer@bsu-ucs.uucp (Leslie Ramer)
Newsgroups: comp.theory.dynamic-sys,sci.math,sci.physics
Subject: Re: square roots by hand or computer
Message-ID: <1991Mar14.113902.97@bsu-ucs.uucp>
Date: 14 Mar 91 11:39:02 GMT
References: <1991Feb28.220523.6184@zaphod.mps.ohio-state.edu> <1991Mar1.001103.6341@cec1.wustl.edu>
Lines: 106

In article <1991Mar1.001103.6341@cec1.wustl.edu>, amc4919@cec_ss1.wustl.edu (Adam M. Costello) writes:
> I have seen several programs posted that implement the square-root-by-hand-
> one-digit-at-a-time algorithm.  This very same algorithm becomes much, MUCH
> simpler in base 2, both for a computer and on paper.  Try it.
> Since base-conversions are easy, I'd say this is the way to go.
> AMC

I would much rather use Newton's method to find the square root or any other
root for that matter.  Newton's method finds the zeros or roots of a function.
Therefore a function that has a zero at the square root of a number, say A,
is desired.

i.e.
 2
X  = A
        2
f(x) = X - A

The general form of Newton's method is as follows:

             f( X  )
                 n
X    = X  - ---------
 n+1    n    f'( X )
                  n

f'(x) = 2X

Plugging this in:
              2
             X  - A
              n
X    = X  - --------
 n+1    n     2 X                     Form 1)
                 n

         2
        X  + A
         n
X    = --------                       Form 2)
 n+1     2 X
            n

        1           A
X   =  --- ( X  + ----- )             Form 3)
 n+1    2     n     X
                     n


Now the only problem is a starting value.  A decent starting value is 1.
If one were to choose zero the sequence would bomb out because of a divide
by zero that would be required to determine the next approximation.

Form 3) was known by Heron(?) before Christ's birth.


X  = 1
 0

Suppose you wished to know the square root of two. ( A = 2) then plugging that
into the different forms.


the sequence would progress as follows:

n)  0   1   2    3     4        ...

        3   17   577   665857
    1 , - , -- , --- , ------ , ...
        2   12   408   470832

I really don't care to take it out any further...  according to my calculator,
the square root of 2 is approximately 1.414213562.

the approximations represented in decimal form are:

 n      decimal equivalence
---    ---------------------
 0      1.0
 1      1.5  
 2      1.416666667
 3      1.414215686
 4      1.414213562

The fourth approximation has already surpassed the accuracy of my calculator.
Newton's method is easily appreciable.  If you were to program this into a
computer, you would probably generate the sequence via floating point numbers.
When the approximations are "close enough" then you can have the program end
and report back the approximated square root.

If you are advanced enough to do a base conversion, you more than likely can
easily apply this method.  The choice is yours.  Moreover, your choice should
hinge more upon the application than anything else.  I usually use pre-packaged
routines in my programming, but they can't always be trusted.  I have found
the packages on my computer and most others very reliable, though.

Leslie Ramer,
Ball State University, Muncie, IN

-- 

"No one runs so fast as he that is chased."
           ._
|  .-..-.  | | .-,.-.-..-..-. 00LHRAMER@bsu-ucs.bsu.edu
|  +-'`-,  |_' .-+| | |+-'|   00LHRAMER@bsu-ucs.UUCP
|__`-'`-'  | \ `.|| | |`-'|   00LHRAMER@bsuvax1.bitnet