Xref: utzoo comp.theory.dynamic-sys:185 sci.math:15779 sci.physics:17502
Path: utzoo!news-server.csri.toronto.edu!rutgers!dimacs.rutgers.edu!seismo!uunet!orca!mesa!rthomson
From: rthomson@mesa.dsd.es.com (Rich Thomson)
Newsgroups: comp.theory.dynamic-sys,sci.math,sci.physics
Subject: Re: square roots by hand or computer
Message-ID: <1991Mar15.063023.6605@dsd.es.com>
Date: 15 Mar 91 06:30:23 GMT
References: <1991Feb28.220523.6184@zaphod.mps.ohio-state.edu> <1991Mar1.001103.6341@cec1.wustl.edu> <1991Mar14.113902.97@bsu-ucs.uucp>
Sender: usenet@dsd.es.com
Reply-To: rthomson@dsd.es.com (Rich Thomson)
Organization: Design Systems Division, Evans & Sutherland, SLC, UT
Lines: 67
Nntp-Posting-Host: 130.187.85.21

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. [...]

Well Newton's method has some interesting properties of its own (as
I'm sure many readers of comp.theory.dynamic-sys are aware).

>Now the only problem is a starting value.  A decent starting value is 1.

If you play with Newton's method long enough you come to realize that,
in general, picking a starting value isn't always obvious.  In
general, you pick a starting value that is "close" to the desired root
of the function.  If you have no idea where the roots of the function
lie, then you may be in trouble.  Newton's method may fail to
converge.  In fact, many interesting fractal images have been computed
for simple functions like z^3 = 0, with z being a complex number.

You find that if you pick points close to any one of the three zeros,
they converge as expected.  The wacky stuff happens at the boundaries
between the basins of attraction for these three roots.  You might
expect the basins of attraction for the three roots to carve the
complex plane into 3 simple regions; in fact the regions are far from
simple and the boundary often has fractal qualities (whether or not
it is a true fractal, i.e. a Hausdorff dimension different from its
covering dimension, I don't know).  Along this boundary region you can
find points arbitrarily close to each other that converge to different
roots.

A different way to compute square roots (and other rational or
non-rational numbers) is through the methods of continued fractions.
If I remember correctly, the continued fraction expansion of Sqrt[2]
is [1,2,2,2,....], where the notation [a0, a1, a2, ...] represents a
continued fraction expansion:

    a0 +         1
	 ------------------
	 a1 +       1
	      -------------
	      a2 +     1
		   --------
		   a3 + ...

The first few terms of the continued fraction expansion are:

[1]		1	1.0
[1,2]		3/2	1.5
[1,2,2]		7/5	1.4
[1,2,2,2]	17/12	1.4166667
[1,2,2,2,2]	41/29	1.4137931
[1,2,2,2,2,2]	99/70	1.4142857

This doesn't converge as quickly as the sequence you give, but it
still interesting.

I think it turns out that non-rational numbers have a continued
fraction expansion that is eventually periodic (i.e. after a finite
number of coefficients in the expansion, a block of coefficients
repeats infinitely), while all rational numbers have a finite
continued fraction expansion.

							-- Rich
-- 
  ``Read my MIPS -- no new VAXes!!'' -- George Bush after sniffing freon
	    Disclaimer: I speak for myself, except as noted.
UUCP: ...!uunet!dsd.es.com!rthomson		Rich Thomson
ARPA: rthomson@dsd.es.com			PEXt Programmer