Ken Ward's Mathematics Pages

Number Theory Continued Fractions

Page Contents

Idea of Continued Fractions
Infinite, Finite, Convergent and Divergent Continued Fractions
Recursion Formula
Computing Continued Fractions
Computing Continued Fractions Using a Calculator
Notation

Idea of Continued Fractions

Once again, we aren't embarrassed to begin with trivial examples. The first two examples are trivial and the third isn't.
If we a decimal number, say 0.5, we can express it as:
0.5= cf1

[1.1]
That is as a double reciprocal (a=1/1/a).

And by evaluating the lower fraction, 1/0.5, we get:
0.5=1/2,
which is the fractional expression for 0.5.

As it happens, the reciprocal of 0.5 is 2, that is, the calculation works out even because the fraction terminates quite quickly.
■

If we take 0.75 as our new decimal, then we will need to continue the fraction:
0.75=

[1.2]

0.75 goes once into 1 and leaves a remainder 0.25. That is 1/0.75=1+0.25/0.75
0.75=

[1.3]

Writing 0.25/0.75 as a double reciprocal: 1/1/0.25/0.75=1/0.75/0.25
0.75=

[1.4]
Because 0.75/0.25=3, the fraction terminates, and we have:
0.75=

[1.5]

We need to work out the final fraction. And beginning at the bottom, we have 1+1/3=4/3. And 1/(4/3)=3/4, which as know is the fractional representation of 0.75.
■
Our next problem is to convert 0.5385 to a fraction.
The first double reciprocal:
0.5385=

[1.6]

0.5385=1+1/1/0.8571
0.5385=

[1.7]

1/0.8571=1+1/0.1667 (we note something that is going to work out soon!)
0.5385=

[1.8]

1/0.1667=6 (to 4 decimal places. See below), so:
0.5385=

[1.9]

Working out the fraction from the bottom 1+1/6=7/6. 1+1/7/6=13/7. And finally, 1/13/7=7/13.

So 0.5385=7/13 (to 4 decimal places)
■

A note on accuracy

[This note isn't particularly about continued fractions, but about using approximations in the calculations.]

Previously, our continued fractions terminated accurately. Here, I have worked to 4 decimal places with a calculator, and the continued fraction terminated, and gave us 7/13. To 4 decimal places, 1/0.1667=6, but this is an approximation.

Window's calculator gives 9/13=0.538461... and rounded to 4 places is 0.5385.

Infinite, Finite, Convergent and Divergent Continued Fractions

1/4, can be written as a continued fractions as:
[0,4]
where the 0 shows there is not integer part and the 4 is the first denominator. So:
1/4=[0,4]
1/4 forms a finite continued fraction because the number of terms is finite (actually 2).

Continued fractions of irrational numbers are infinite, because the number of terms never ends. For instance, the continued fractions for π and √2 are infinite.

Nonetheless for the continued fraction being infinite, or finite, it may converge or diverge. It diverges when the resulting fractions oscillate or become infinite. Otherwise, it converges when the values of the continued fraction approach a limit.

For instance, the continued fraction √2=[1,2,2...], is infinite, but converges to a value.

A regular continued fraction is one where all the terms are natural numbers, except the first, which can be zero. Regular continued fractions always converge.
■

Recursion Formula

The following recursion formula applies to continued fractions:

[3.1]
For instance,
π=[3, 7, 15, 1, 292...]
=3+1/[7, 15, 1, 292...]
=3+1/(7+1/[15, 1, 292...])
=3+1(7+1/(15+1/([1, 292...]) )
■

Computing Continued Fractions

We seek the continued fraction for a number α. First:

[4.1]
Where [α] means the floor of α (the greatest integer less than alpha, using Gaussean brackets). r₁ is the remainder.
Set a₀=[α]

Next

[4.2]

In general:

[4.3]
The algorithm stops when the remainder is zero. This is true when integers are used, but not when decimals are used, because of rounding errors.
■

Example 1

We seek the contined fraction for α=23/17
23/17=1+6/17
17/6=2+5/6
6/5=1+1/5
5=5+0

The algorithm stops at zero. The continued fraction for 23/17 is [1,2,1]

Example 2

α=1.71
Working to 4 decimal places:

1.71=1+0.71
1/0.71=1+0.4085
1/0.4085=2+0.4483
1/0.4483=2+0.2308
1/0.2308=4+0.3333
1/0.3333=3+0
The continued fraction is [1,1,2,2,4,3]

Computing Continued Fractions Using a Calculator

The only point here is that when working with decimals, errors may prevent the algorithm from reaching zero, at least in a reasonable number of steps.
We seek the continued fraction for 3.1415926536, which is pi to 10 decimal places.

In the following table, a is the term of the continued fraction, and r is the fractional remainder.

k	a_k	r_k	Remarks
1	3	0.1415926536	First, we write the integer part, 3, under a and the fraction remaining under r.
2	7	0.0625133054	Take the reciprocal of r₁, and write the integer part under a₂, and the fraction under r₂.
3	15	0.9965945426	We continue, taking the reciprocal of r₂ and writing the integral part under a₃ and the fraction under r₃.
4	1	0.0034170942
5	292	0.6463074972
6	1	0.5472511217
7	1	0.8273146648

The continued fraction for 3.1415926536 is [3,7,15,1,292,1,1]. For reasons not explained here, but explained later, we cannot go further with our calculations because the error in the fraction becomes less than the expected error in our original number, so we find ourselves chasing rounding errors, rather than obtaining a more accurate representation of the number.

[3,7,15,1,292,1,1] is an approximation to the continued fraction for pi (the true continued fraction is infinite, of course).

As it happens, the above table was written by a spreadsheet, not a calculator!

Notation

Here are some definitions related to continued fractions, to assist talking about them. (I have tended to be informal in these pages).
A representation of a number, α, as a continued fraction:

is called a representation in canonical form. a₀, a₁, etc are called terms.

An infinite continued fraction is one with an infinite number of terms (the number, α is then an irrational number).

A finite continued fraction is one with a finite number of terms. The number, α, is therefore a rational number.

The value p_k/q_k is called the canonical approximation, or the k-th convergent.

The values p_k and q_k are called the k-th iteration (of p or q).

For the sake of clarification, a recursion produces a new value from previous values. A recrusive formula produces new values from previous ones. An iteration produces an updated value. An iterative formula produces an updated value from a previous one, usually more accurate. The difference between iteration and recursion is not always clear. The p's and k's are called iterations because they are updated, more accurate values for the numerator and the denominator. The recursive formula above, produces new terms for the continued fraction from previous values.

Number Theory Contents

Ken Ward's Mathematics Pages