Wednesday, August 25, 2021

Calculating continued fractions

 I've been playing with continued fractions.  The golden ratio is one of the simplest examples.

Substituting the whole right-hand side for the denominator on the right:

And here is sqrt(3) for another.  I find the square root symbol to be a bit of a distraction, so I substituted x for sqrt(3).

The standard notation for this is [1;(1,2)].  Here is the derivation for this example:

At this point, the trick is to add and subtract 1 in the denominator on the right-hand side  

But (x - 1)/2 = 1/(x + 1), and after another round of add and subtract we have

We are done because x - 1 appears on both sides.

Then to evaluate it we must chop off the continuation somewhere.  For this example, there are two different chains of rational approximations to sqrt(3).  Here is one

I think I finally understand how the derivation works.  I've done a number of examples with as many as 8 terms in the continued part.  This resource was very helpful, since it has the correct answers.

I also wrote a simple Python script to evaluate a continued fraction based on the coefficients, which does the somewhat tedious calculations.

I wrote this up as a pdf on GitHub, and the script is a gist here.

And finally, just note that the existence of a continued fraction that continues forever is a proof of irrationality.  All of the integers that are not perfect squares are irrational, and they all have continued fraction representations.

[Sorry for the large image sizes.  They are screenshots from my pdf, which blogger insists on making giant size even when "small".  I know, I know, MathJax, but ... ].