Associated Topics || Dr. Math Home || Search Dr. Math

### Newton's Method and Continued Fractions

```
Date: 10/06/1999 at 01:58:37
From: Robert Kaluhiokalani
Subject: Comment about sqrt() and Decimal to Fraction Conversion

Dear Math Doctors,

First, in the response given to 'Square Roots Without a Calculator'

http://mathforum.org/library/drmath/view/51890.html

I was intrigued by the use of the 'High School Method' used to solve
square roots. Now I understand that you tend to gear your replies so
that they are consonant with the expertise of the person who's asking
the question, so I can understand that you wouldn't have presented the
Newton algorithm. On the other hand, that was an algorithm I thought
for sure I'd see presented, mostly because I was under the impression
that it had been published somewhere. Perhaps I'm wrong.

A few years ago I didn't have a calculator handy and I needed to
calculate the square root of a few numbers. I knew that there was such
an algorithm, but I couldn't remember it off the top of my head, so I
resorted to devising my own. I was sure that with a few algebraic
manipulations I would hit paydirt (which I did), and that the result
would look something like the square root algorithm I had once seen
but now forgotten. Well, after a little more playing around I ended up
with the following:

f(0) = 1
g(0) = 1

f(i+1) = f(i) + g(i)*n
g(i+1) = f(i) + g(i)

sqrt(n) = f(x)/g(x)

where n is the number your finding the square root of, and x is
proportional to the decimal precision.

Example:

n = 2

f(1) = 1 + (1*2)   = 3
g(1) = 1 + 1       = 2

f(2) = 3 + (2*2)   = 7
g(2) = 3+2         = 5

...

f(5) = 41 + (29*2) = 99
g(5) = 41 + 29     = 70

f(5)/g(5) = 1.414285714...

My question: Have you seen this before? Not that it's something novel,
but I just would think something as trivial as this would make it into
a few more books than it evidently has. I also might point out that in
terms of pencil-and-paper math, this has no round-off error (until the
last step, at least). Did I miss an important deficiency?

Second, in your response to 'Decimal To Fraction Conversion'

http://mathforum.org/library/drmath/view/51886.html

I'm curious about the choice to use continued fractions. A method was
presented equivalent to the following:

0.17893403489 = 17893403489/10^11

since 10^n = 2^n*5^n, would it not be an easy task to reduce this
fraction? You have a prime factor representation of the denominator
already, so no new work needs to be done but to see if the numerator
is divisible by 2 or 5.

Incidentally, once again lack of information prompted me to devise my
own procedure. But this time it was with repeating sequences. I ended
up dividing the cycle by a string of that number of 9's.

Example:

.142857142... = 142857/999999 = 15873/111111 = ... = 1/7

Now at one point I decided to use the continued fraction technique
similar to the one you presented to reduce the fraction. It always
reduced it, but not to where the GCD was 1. If this also holds for the
case of non-repeating sequences, then what value does it have at all?
I did notice that in the non-repeating case the continued fraction
looks remarkably like the Euclidean Algorithm, so maybe this is why it
works.

One last thing, merely for entertainment: Check out the cycle that
1/109 makes. Kind of a pseudo-irrational, at least if you don't know
any better.
```

```
Date: 10/06/1999 at 10:17:21
From: Doctor Rob
Subject: Re: Comment about sqrt() and Decimal to Fraction Conversion

Thanks for writing to Ask Dr. Math, Robert.

You make a number of interesting points, which I will try to address
in turn.

First, you bemoan the absence of Newton's Method in our archives.
Actually, it's there. It's on our "Square/Cube Roots Without a
Calculator" Web page at:

http://mathforum.org/dr.math/faq/faq.sqrt.by.hand.html

You seem to be unfamiliar with Newton's Method. This is it:

If f(x) is a function whose root you are seeking (in our case, x^2-n),
then if you start with a close enough approximation x(0), then the
iteration

x(i+1) = x(i) - f(x(i))/f'(x(i))

for i = 0, 1, 2, ... will converge to a root, and the convergence is
"quadratic," in the sense that each x(i+1) will have about double the
accuracy of x(i).

In our case, this becomes

x(i+1) = x(i) - [x(i)^2-n]/[2*x(i)]
= [2*x(i)^2 - x(i)^2 + n]/[2(x(i)]
= [x(i)^2+n]/[2*x(i)]
= (1/2)*[x(i) + n/x(i)]

This iteration is described as "guess, divide, and average" on the Web
page near the top. Guess x(i), divide it into n, and average those two
to get x(i+1).

This method is much faster in convergence than the one you give above.
The number of steps required for a certain accuracy r using Newton's
Method is a constant times log_2(r) compared to a constant times r for
your method, and the constants are roughly the same size.

Secondly, you ask if the method you gave above is known to us. The
answer is, not precisely that method, but strongly related ones. By
the way, the convergence of your method for large values of n is
extremely slow. For example, I tried n = 17, and got the following
values for f(i)/g(i):

i    f(i)/g(i)
--    ---------
0    1.0000000000000
1    9.000000000
2    2.6000000000
3    5.444444444
4    3.48275862
5    4.569230769
6    3.87292817679558
7    4.2834467
8    4.02832618
9    4.18197336975
10    4.1448847
11    4.10988502
12    4.1311859
13    4.118187543
14    4.1261066
15    4.12127725044
16    4.1242206
17    4.122426058
18    4.12351995
19    4.122853067

So you see that even after 19 steps, we only have 4 digits of
accuracy. It is even worse for larger n. For n = 5428, after 19 steps
we have zero digits of accuracy. It takes more than 60 steps to get
even one digit of accuracy.

There is a related algorithm that computes the square root more
rapidly than that yours, which is based on the continued fraction
expansion of sqrt(n). It has the form

f(0) = 1
g(0) = 0

f(1) = floor(sqrt[n])
g(1) = 1

f(i+1) = a(i)*f(i) + f(i-1)
g(i+1) = a(i)*g(i) + g(i-1)

where a(i) are the partial quotients in the continued fraction
expansion of sqrt(n).

expressing a decimal as a fraction with a small denominator.
the numerator is divisible by neither 2 (last digit is odd) nor 5
(last digit isn't 0 or 5), this fraction is in lowest terms. Its
12-digit denominator is quite large compared to the answer 141/788 =
0.17893401015..., which agrees with it to seven decimal places,
produced by the CFA.

Your method using repeating sequences is covered in Section II.B on
the FAQ page on Fractions, Decimals, Percentages:

http://mathforum.org/dr.math/faq/faq.fractions.html

The value of applying the CFA to non-repeating decimals is that you
can find a fraction that is as close as you like in value to that
decimal, and with a very small denominator.

The results of the CFA must always be a fraction reduced to lowest
in very short order, and if you start with .4444444..., it will give
you 4/9 very quickly. I don't understand your comment about using an
algorithm similar to the CFA, and getting GCD other than 1.

The relation between the CFA and the Extended Euclidean Algorithm is
an extremely close one, and, yes, that is what makes it both fast and
effective.

further, feel free to write again.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sequences, Series
High School Square & Cube Roots
Middle School Fractions
Middle School Square Roots

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search