# A little about continued fractions

`(This file is best viewed in a nonproportional font.)`

### Definition of Continued Fractions

`Continued fractions have been used for an amazing variety of things, includingsolving quadratic equations, proving that Pi is irrational, calculating thedate of Easter, predicting eclipses, and investigating chaos.`
Homepage
`So what is a continued fraction?A finite continued fraction f can be written like so:f = a_0 + b_1          ____________          a_1 + b_2                ___________                a_2 + b_3                      _________                      a_3 + .                              .                                .                                    a_{m-1} +   b_m                                                ____   .                                                a_mEquivalently, it may be written on one line using parentheses:f = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ... a_{m-1} + b_m/a_m))) ... ),where there are m-1 right parentheses at the end.Many books prefer to write this using subscripted plus signs like so:f = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+ ... _+ b_m/a_m  .If we stop the computation at a_n and b_n with 0 <= n <= m, we have producedthe n-th  "convergent" of f, which we write f_n.Thus f_0 = a_0, andf_1 = a_0 + b_1/a_1.For 1 <= n <= m,f_n = a_0 + b_1            ____________            a_1 + b_2                  ______________                  a_2 + b_3                        _________                        a_3 + .                                .                                  .                                                        a_{n-1) +  b_n                                                 ____   ,                                                 a_norf_n = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ... a_{n-1} + b_n/a_n))) ... ),orf = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+ ... _+ b_n/a_n  .An infinite continued fraction is written in the same way except that it doesnot terminate.  So it can be written as f = a_0 + b_1          ____________          a_1 + b_2                ___________                a_2 + b_3                      ___________                      a_3 + .                              .                                .                                   orf = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ...    or f = a_0 + b_1/a_1 _+ b_2/a_2 _+ b_3/a_3 _+  ...  .One might wonder what this means.  If f is an infinite continued fraction,you can define its convergents using the same equations as above.Consider the infinite sequence f_0, f_1, f_2, ...   .  If this sequenceconverges to some fixed value, we assign that value to f.If a continued fraction (either finite or infinite) has all its b_i equal to1, and all its a_i are integers, and all the a_i with i > 0 are non-negative,it is called a simple continued fraction.  Simple continued fractions areoften written by listing their a_i, like so:.f = [a_0, a_1, a_2, ... a_m] for a finite continued fraction,or f = [a_0, a_1, a_2, ...] for an infinite continued fraction.All simple continued fractions converge to some value.Continued fractions that are not simple are called general continuedfractions.Simple continued fractions are important in number theory.  They can be usedto approximate irrational numbers by fractions, to prove that particularirrational numbers are in fact irrational and to solve Diophantine equations.General continued fractions are sometimes used in analysis to find the valueof special functions in regions where power series converge poorly.  They arerelated to the theory of how to approximate functions with ratios of twopolynomials (rational approximation or Pade approximation).  Any power seriescan be rewritten as a general continued fraction.  A special function with athree term recursion relation (such as an orthogonal polynomial), can bewritten as a general continued fraction.  General continued fractions alsocrop up when one is inverting a tridiagonal matrix, and as a substitute forthe transfer matrix method.`

#### Sample Program

Here is a program written in C that uses continued fractions to compute arctangents and error functions. It is a text file. It uses the forward recurrence algorithm described below. I was moved to write this program after Bob Delaney wrote a continued fraction program to compute arctangents.

` `

### How to evaluate continued fractions

` What one actually evaluates is a convergent  f_n.  There are two common ways of doing this, which Jones and Thron call the "backward recurrence algorithm" and the "forward recurrence algorithm".`

#### Backward Recurrence Algorithm

`This is the more intuitive method. It consists of evaluating the expression for f_n by starting at the end (or bottom) and working ones way back to the beginning (or top). Thus one first finds b_n / a/n. Then one adds a_(n-1), takes the reciprocal, multiplies by b_(n-1) adds a_(n-2) and so on...One advantage of this method is that it is easy to understand and program. Also, according to Jones and Thron (page 26), this method is often more numerically stable than the forward recurrence method.  Its big disadvantage is that you don't necessarily know in advance how big a value of n you need to get a given accuracy.If you have found f_n using this method, you need to start over from scratch to find f_(n+1).`

#### Forward recurrence Algorithm

`This method allows one to evaluate the convergents f-1, f_2 and so on recursively.The advantage of this method is that the work done in finding f_n can be reused if one then decides to find f_(n+1).  A possible disadvantage, according to Jones and Thron, is that in some situations, it may be less numerically stable than the backward recurrence algorithm.We write the convergent f_i as a fraction f_i = P_i/Q_i.f_0 = a_0 so we can take P_0 = a_0 and Q_0 = 1.f_1 = (a_1 * a_0 + b_1)/a_1.So we can take P_1 = a_1*a_0 + b_1 and Q_1 = a_1.Then it can be shown by mathematical induction (proof below) that, for i > 1P_{i+1} = a_{i+1} * P_i  +  b_{i+1} * P_{i-1}          (1a)andQ_{i+1} = a_{i+1} * Q_i  +  b_{i+1} * Q_{i-1} .        (1b)If you define P_{-1} = 1 and Q_{-1} = 0 you can use these recursion relationsfor i > 0.In this way, if you want just one more convergent, you need to do just alittle more work instead of starting over from the beginning.  These recursionrelations can be formally rewritten in terms of 2*2 matrices:___     ___     ___             ___   ___     ___ | P_{i+1} |  =  | a_{i+1}  b_{i+1}|   | P_i     || P_i     |     | 1        0      |   | P_{i-1} |---     ---     ---             ---   ---     --- and similarly___     ___     ___             ___   ___     ___ | Q_{i+1} |  =  | a_{i+1}  b_{i+1}|   | Q_i     || Q_i     |     | 1        0      |   | Q_{i-1} |   .---     ---     ---             ---   ---     ---Proof of the recursion relationships (1)First we show that they are true for i=2.We to write f_2  as f_2 = P_2/Q_2.What follows looks lengthy, but only because I wrote out all the steps.f_2 = a_0 + b_1/(a_1 + b_2/a_2)= a_0 + b_1/[(a_2*a_1 +b_2)/a_2]= a_0 + b_1*a_2/(a_2*a_1 +b_2)= (a_2*a_1*a_0 + b_2*a_0 + b_1*a_2) / (a_2*a_1 + b_2)= [a_2*(a_1*a_0 + b_1) + b_2*a_0] / [a_2*a_1 + b_2*1]= [a_2*P_1 + b_2*P_0] / [a_2*Q_1 + b_2*Q_0].So we can take P_2 = a_2*P_1 + b_2*P_0 and Q_2 = a_2*Q_1 + b_2*Q_0.So equations(1) are true for i = 2.  Now assume that they're true for i =1, 2, ... n.  Then let's show that they must also be true for i = n+1.f_{n+1} = a_0 + b_1                ____________                a_1 + b_2                      ____________                      a_2 + b_3                            _____________                            a_3 + .                                    .                                      .                                                                   a_{n-1} + b_n                                                    _____________                                                    a_n + b_{n+1}                                                          _______   .                                                          a_{n+1}But, similarly to what we just did,b_n____________a_n + b_{n+1}      _______      a_{n+1}= b_n / [a_n + b_{n+1}/a_{n+1}]= b_n / [(a_{n+1}*a_n + b_{n+1})/a_{n+1}]= a_{n+1}*b_n / (a_{n+1}*a_n + b_{n+1})= b'_n/a'_nwhere a'_n = a_{n+1}*a_n + b_{n+1}and b'_n = a_{n+1}*b_n.So f_{n+1} can be put in the same form as an nth convergent except with a_nreplaced by a'_n and b_n replaced by b'_n:f_{n+1} = a_0 +  b_1                 ____________                 a_1 + b_2                       ________________                       a_2 + b_3                             _____________                             a_3 + .                                     .                                       .                                                                        a_{n-1} + b'_n                                                     _____   .                                                     a'_nSo, since the recursion relations (1) are assumed to be true for 1 < i <= n,we can rewrite f_{n+1} asf_{n+1} = [a'_n*P_{n-1} + b'_n*P_{n-2}] / [a'_n*Q_{n-1} + b'_n*Q_{n-2}].That is, we can takeP_{n+1} =  a'_n*P_{n-1} + b'_n*P_{n-2} andQ_{n+1} = a'_n*Q_{n-1} + b'_n*Q_{n-2} .Now work with these expressions for P_{n+1} and Q_{n+1}.  Start with P_{n+1}.Remembering what a'_n and b'_n are:P_{n+1} = [a_{n+1}*a_n + b_{n+1}]*P_{n-1} + [a_{n+1}*b_n]*P_{n-2}= a_{n+1}*[a_n*P_{n-1} + b_n*P_{n-2}] + b_{n+1}*P_{n-1} .But a_n*P_{n-1} + b_n*P_{n-2} = P_n, since (1a) is assumed to be true for1 < i <= n.  SoP_{n+1} = a_{n+1}*P_n + b_{n+1}*P_{n-1}, which is (1a) for i = n+1.Similarly,Q_{n+1} = a'_n*Q_{n-1} + b'_n*Q_{n-2}= [a_{n+1}*a_n + b_{n+1}]*Q_{n-1} + [a_{n+1}*b_n]*Q_{n-2}= a_{n+1}*[a_n*Q_{n-1} + b_n*Q_{n-2}] + b_{n+1}*Q_{n-1}= a_{n+1}*Q_n + b_{n+1}*Q_{n-1}, which is (1b) for i = n+1.So we have shown that the recursion relations (1) are true for i=2 and that ifthey are true for i = 1, 2, ... n they are also true for i=n+1.  So, bymathematical induction, they are true for all n > 1.Now, if you arbitrarily define P_-1 = 1 and Q_-1 = 0, P_1 = a_1*a_0 + b_1 = a_1*a_0 + b_1*1 = a_1*P_0 + b_1*P_-1andQ_1 = a_1 = a_1*1 +b_1*0 = a_1*Q_0 + b_1*Q_-1 .So with these arbitrary definitions of P_-1 and Q_-1 the recursion relation (1)works for all n>= 1.`

### References

• `"Continued Fractions" by C. D. Olds, copyright 1963.This little book is oriented towards number theory.  It can be understoodby bright high school students.  It's also a good introduction to continuedfractions.  Unfortunately, it's out of print.`
• `"Continued Fractions" by A. Ya. Khinchin, 3rd edition.This elegant little book, available from Dover Publications, is exclusively about simple continued fractions.  `
• `"Die Lehre von den Kettenbruche" by Oskar Perron. Volume 1 (1954) and volume 2 (1957). In German.  Apparently, this was for decades (the first edition was in 1913)the book in the field.  This is the only one of the books here I haven't used.`
• `"Analytic Theory of Continued Fractions" by H. S. Wall (1948).As the title indicates, this book is about continued fractions in "analysis", rather than number theory. Thus it is about generalized continued fractions and their connections to power series, hypergeometric functions, orthogonal polynomials, infinite matrices, Pade approximants, definite integrals, and so on. It was reprinted in 2000 by the American Mathematical Society.`
• `"Continued Fractions Analytical Theory and Applications (volume 11 ofEncyclopedia of Mathematics and Its Applications)" by William B. Jones,copyright 1980.  This is a tome.  Unfortunately, it also is out of print.  Despite its length,it is not completely self-contained; for example it uses results from the bookby Wall.`
• `"Continued Fractions  Volume 1: Convergence Theory", 2nd edition, 2008, byLisa Lorentzen and Haakon Waadeland.Aimed at readers "in or near mathematics".`
• `"Continued Fractions" article in Eric's World of Mathematics `
<To get my e-mail address, replace "at" with "@" & remove the spaces:
christopher e reed at cs . com>
This page was created on June 9, 2002. It was changed/fiddled with on October 23, 2010.
Homepage
ċ
confrac.txt
(4k)
Christopher Reed,
Jan 22, 2009, 11:16 PM