A Special Continued Fraction for Square Root |
Note: more than any other idea or feature of Ted's World, it is the following discovery and a desire to share it that prompted me to set up a website in the first place. Subsequently I have found other web pages featuring this method; but I believe that you will find this one easiest to read.
Simple Elegance
The square root of any positive number can be expressed as a
continued fraction. The well-known Babylonian equation
is one of those:
The approximation of the root is e. To calculate sqrt(27) with an estimate of 5:
For the second iteration, 5.2 would become the new e, and so on. This procedure is described on a multitude of web pages; so I'll not elaborate further. Equally many sites also discuss other continued fractions, detailing exotic constructs such as this approximation of sqrt(19):
This is indeed an interesting pattern, having a "period" of six iterations. Much less frequently mentioned is this fact:
For reasons unclear to me, most demonstrations of continued fractions feature a numerator of 1. Well, that restriction might be the natural order of things for the mathematical highbrows; but it is not the only valid setup. Reducing our own CF to something useful involves just a simple adjustment to the Babylonian equation:
In this arrangement, if e is the greatest integer which square is less than n, then the iterations approximate only the fractional, or decimal portion of the root:
Now that is elegant!
In the example, 4 happens to be the integer closest to the root, but in fact e can be any positive value. The following continued fractions all represent sqrt(19):
Notice that e does not have to be less than the actual root. If it is greater, then the continued fraction will have a negative numerator.
When e is less than sqrt(n), then successive approximations oscillate around the root, starting below it; otherwise, the series converges downward toward the root:
The iterations are quadratic; that is, the relative accuracy doubles with each loop.
When the digits in a continued fraction never change, calculating its value becomes a simple procedure. This fact is put to good use on these other pages: