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).


Next, you ask about the continued fraction algorithm (CFA) for 
expressing a decimal as a fraction with a small denominator. 
Particularly, you asked about the fraction 17893403489/10^11. Since 
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 
terms. If you start with .142857142857142857..., it will produce 1/7 
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.

Thanks for your comments. If you wish to discuss these matters 
further, feel free to write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/