Xref: utzoo comp.theory.dynamic-sys:192 sci.math:15800 sci.physics:17533 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!bcm!dimacs.rutgers.edu!aramis.rutgers.edu!gauss.rutgers.edu!math.rutgers.edu!bumby From: bumby@math.rutgers.edu (Richard Bumby) Newsgroups: comp.theory.dynamic-sys,sci.math,sci.physics Subject: Re: square roots by hand or computer Message-ID: Date: 16 Mar 91 00:50:48 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> Followup-To: comp.theory.dynamic-sys Organization: Rutgers Univ., New Brunswick, N.J. Lines: 48 Cc: bumby In article <1991Mar15.063023.6605@dsd.es.com> rthomson@mesa.dsd.es.com (Rich Thomson) writes: > . . . > > If you play with Newton's method long enough you come to realize that, > in general, picking a starting value isn't always obvious. . . . Some cases are reasonably robust, however. For example the largest root of a polynomial with all roots real will be approached by Newton's method with a starting value larger than that root. > . . . > > 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,....], . . . It is. > . . . > > This doesn't converge as quickly as the sequence you give, but it > still interesting. > The rate of convergence is easily worked out, and of the form c^n if n terms are taken. This is fine for ordinary machine precision, but wasteful if you want millions of digits. > I think it turns out that non-rational numbers have a continued > fraction expansion that is eventually periodic . . . It is easy (after Euler) to show that such numbers must be quadratic irrationals. Lagrange showed that all quadratic irrationals have continued fractions which are eventually periodic, and conditions for pure periodicity have been worked out. Perron's book gives Galois as the source for this work, as well as for determining the effect of reversing the period. The analytic theory allows the "digits" (called "partial quotients") of some other numbers (for example e) to be determined, but the expansion of pi or the cube root of 2 seems to be random. -- --R. T. Bumby ** Math ** Rutgers ** New Brunswick ** NJ08903 ** USA -- above postal address abbreviated by internet to bumby@math.rutgers.edu voice: 908-932-0277 (but only when I am in my office)