confracs
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, including
solving quadratic equations, proving that Pi is irrational, calculating the
date of Easter, predicting eclipses, and investigating chaos.
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_m
Equivalently, 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 produced
the n-th "convergent" of f, which we write f_n.
Thus f_0 = a_0, and
f_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_n
or
f_n = a_0 + b_1/(a_1 + b_2/(a_2 + b_3/( ... a_{n-1} + b_n/a_n))) ... ),
or
f = 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 does
not terminate. So it can be written as
f = a_0 + b_1
____________
a_1 + b_2
___________
a_2 + b_3
___________
a_3 + .
.
.
or
f = 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 sequence
converges to some fixed value, we assign that value to f.
If a continued fraction (either finite or infinite) has all its b_i equal to
1, 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 are
often 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 continued
fractions.
Simple continued fractions are important in number theory. They can be used
to approximate irrational numbers by fractions, to prove that particular
irrational numbers are in fact irrational and to solve Diophantine equations.
General continued fractions are sometimes used in analysis to find the value
of special functions in regions where power series converge poorly. They are
related to the theory of how to approximate functions with ratios of two
polynomials (rational approximation or Pade approximation). Any power series
can be rewritten as a general continued fraction. A special function with a
three term recursion relation (such as an orthogonal polynomial), can be
written as a general continued fraction. General continued fractions also
crop up when one is inverting a tridiagonal matrix, and as a substitute for
the 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 > 1
P_{i+1} = a_{i+1} * P_i + b_{i+1} * P_{i-1} (1a)
and
Q_{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 relations
for i > 0.
In this way, if you want just one more convergent, you need to do just a
little more work instead of starting over from the beginning. These recursion
relations 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'_n
where 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_n
replaced 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'_n
So, since the recursion relations (1) are assumed to be true for 1 < i <= n,
we can rewrite f_{n+1} as
f_{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 take
P_{n+1} = a'_n*P_{n-1} + b'_n*P_{n-2} and
Q_{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 for
1 < i <= n. So
P_{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 if
they are true for i = 1, 2, ... n they are also true for i=n+1. So, by
mathematical 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_-1
and
Q_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 understood
by bright high school students. It's also a good introduction to continued
fractions. 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 of
Encyclopedia 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 book
by Wall.
"Continued Fractions Volume 1: Convergence Theory", 2nd edition, 2008, by
Lisa Lorentzen and Haakon Waadeland.
It is 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 December 19, 2020.
