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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.