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.

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_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.

Homepage