§1. Introduction  Lecture XIV  Page 1

Lecture XIV Continued Fractions

On the theory that continued fractions are underused, probably because of their unfamiliarity, I offer the following propaganda session on the relative merits of continued fractions versus other numerical representations.

— Gosper [2]

This venerable subject goes back to the Greeks: Archimedes and Theon of Smyrna (circa 130 A.D.) were suspected of using continued fractions to approximate square roots [5]. Pringsheim [13] states that Cataldi (1613) is the inventor of continued factions. Euler uses the term “continued fractions” (fractio continua) for the first time. Continued factions arose originally in the solution of algebraic equations. It is also widely used in analysis under the “analytic theory of continued fractions”. The classic in the subject is Oskar Perron’s two-volume Die Lehre von den Kettenbrüchen [11, 12], a considerable expansion of the original volume [10]. Other references include Wall [17], Khovanskii [7], Jones and Thron [6], and Lorentzen and Waadeland [9].

Continued fractions is a particular representation of numbers with an implied iterative computational process. It furnishes us with an alternative constructive approach to the subject of computable real numbers (the more obvious approach takes a computable real number to be a computable sequence of bits, say). Gosper [2] is an early advocate of the merits of continued fraction arithmetic, and described algorithms for the basic arithmetic operations. More recently, Vuillemin [16] expanded on these ideas, advocating the use of redundant continued fraction representation.

§1. Introduction

What is a continued fraction? Intuitively, it is a sequence of approximations to a number. For instance, consider the fraction \frac{343}{284} = 1.20774 . . .. To the nearest integer, \frac{343}{284} ∼ 1. More precisely,

\frac{343}{284} = 1 + ϵ_{1}

where 0 ≤ ϵ_{1} < 1 is an error term. The term ϵ_{1} is more precisely given by

\frac{1}{ϵ_{1}} = \frac{284}{59} = 4 + ϵ_{2}

where 0 ≤ ϵ_{2} < 1. The term ϵ_{2} is really

\frac{1}{ϵ_{2}} = \frac{59}{48} = 1 + ϵ_{3}

where 0 ≤ ϵ_{3} < 1. Continuing in this spirit,

\frac{1}{ϵ_{3}} = \frac{48}{11} = 4 + ϵ_{4}, \frac{1}{ϵ_{4}} = \frac{11}{4} = 2 + ϵ_{5}, \frac{1}{ϵ_{5}} = \frac{4}{3} = 1 + ϵ_{6}, \frac{1}{ϵ_{6}} = 3.

Thus we see that

\frac{343}{284} = 1 + \frac{1}{4 + _{\frac{1}{1+_{\frac{1}{4+ \frac{1}{2+ \frac{1}{1+ \frac{1}{3}}}}}}}} .

§2. Extended Numbers  Lecture XIV  Page 2

The expression on the right is called a continued fraction. The reader may notice that we have just carried out the Euclidean algorithm (§II.2) on the pair 343, 284. This connection is no accident. The sequence [1, 4, 1, 4, 2, 1, 3] of quotients obtained in the Euclidean algorithm can be regarded as a representation of 343/282. Furthermore, each initial prefix of this sequence is an approximation — it will be shown that these approximations are the best possible in a suitable sense.

Let us next take an irrational number, \sqrt{2} = 1.414213 . . .. To the nearest integer, \sqrt{2} ∼ 1. Well, it is closer to \sqrt{2} ∼ 1 + \frac{1}{2}. But in fact,

1 + \frac{1}{2 + \frac{1}{2}} ,  1 + \frac{1}{2 + \frac{1}{2+ \frac{1}{2}}} ,  ⋯

are successively better (each improvement is obtained by replacing the rightmost occurrence of ‘2’ with ‘2 + \frac{1}{2}’.) Apparently this process could be continued indefinitely. To see why, note that

\sqrt{2} − 1 = \frac{1}{\sqrt{2} + 1} = \frac{1}{2 + (\sqrt{2} − 1)}

which is a recursive equation in \sqrt{2} − 1. Thus the recursion can be expanded as often as we like. This example shows that a continued fraction is generally an infinite expression.

Our third motivation for continued fractions is to view them as approximate solutions to algebraic equations. Suppose x satisfies the equation X^{2} − 2X − 1 = 0. Then we have

x = 2 + \frac{1}{x}.

We may further expand the x on the right-hand side,

x = 2 + \frac{1}{2 + \frac{1}{x}} = 2 + \frac{1}{2 + \frac{1}{2+ \frac{1}{x}}} = ⋯

By ignoring the trailing x in these continued fractions as negligible, we get a succession of approximations to x:

2, 2 + \frac{1}{2}, 2 + \frac{1}{2 + \frac{1}{2}} , 2 + \frac{1}{2 + \frac{1}{2+ \frac{1}{2}}} , 2 + \frac{1}{2 + _{\frac{1}{2+_{\frac{1}{2+ \frac{1}{2}}}}}} , ⋯

These approximations are

2, \frac{5}{2} = 2.5, \frac{12}{5} = 2.4, \frac{29}{12} = 2.4166 …, \frac{70}{29} = 2.4138 …, ⋯

The reader must have noticed the similarity between x and \sqrt{2} above. Indeed, solving the quadratic equation for x we get x = 1 ± \sqrt{2}. Thus we have obtained a sequence of approximations for x = 1 + \sqrt{2}. We will return to the subject of using continued fractions to solve algebraic equations.

An advantage of continued fractions is illustrated by the nice continued fraction representation of \sqrt{2}: many transcendental numbers such as e, π also have “regularly describable” continued fractions. So for some applications, it may be a more natural representation of numbers than, say, binary or decimal notations.

Exercises

Exercise 1.1: Using the continued fraction expansion approach to find a root of X^{3} − 2X^{2} + 1 Can you find the other roots by a similar approach? HINT: X = 2 − \frac{1}{X^{2}} = · · ·. □

§2. Extended Numbers

We make a small but essential detour. The natural setting for discussing continued fractions involves infinity as a number. Let the set

ℂ̂:= ℂ ∪ {∞}

of extended complex numbers be the set ℂ of complex numbers augmented with a single new point ∞. It has a compact topology, obtained by the “one-point compactification” of the usual topology of ℂ. When we restrict attention to the set ℝ ⊆ ℂ of real numbers, we similarly have the one-point compactification,

ℝ̂:= ℝ ∪ {∞},

the set of extended real numbers. An extended number is finite if it is not equal to ∞ (so finite numbers are just numbers in the usual sense). It is important to realize that we equate ∞ with −∞, in the same way that 0 = −0. It is convenient to further introduce a new symbol ⊥ (called bottom) that is not a number: we call it the indefinite value. Hence we also call an extended number a definite value. With all this, the traditional injunction against dividing by zero is removed and given an algebraic expression:

0/0 = ⊥, x/0 = ∞

where x is any non-zero extended number. Of course, all this begs the question of extending the arithmetic operations to ⊥ as well as ∞. The rule for ⊥ is easy: if any operand equals ⊥, the result of the arithmetic operation is ⊥. For example, x + ⊥ = ⊥ + x = ⊥ for all x. The rule for ∞ is more involved, but could be deduced by using simple limiting arguments. For instance, suppose {a_{i}}, {b_{i}} are monotonic sequences that tend to 0 and to ∞, respectively. Then the sequence {a_{i} + b_{i}} tends to ∞. This gives the rule

0 + ∞ = ∞.

If the monotonic sequence {c_{i}} also tends to ∞, we see that {b_{i} + c_{i}} could tend to any value or to nothing at all. Thus

∞ + ∞ = ⊥.

We have ∞ − ∞ = ∞ ÷ ∞ = ⊥ by the same argument. Similarly, {a_{i}b_{i}} is indefinite, yielding

∞ × 0 = 0 × ∞ = ⊥.

This exhausts all cases where the result is indefinite. A summary of these operations is given in the following tables.

\begin{matrix}+ & 0 & y & ∞ & − & 0 & y & ∞ \\ 0 & 0 & y & ∞ & 0 & 0 & −y & ∞ \\ x & x & x + y & ∞ & x & x & x − y & ∞ \\ ∞ & ∞ & ∞ & ⊥ & ∞ & ∞ & ∞ & ⊥ \\ × & 0 & y & ∞ & ÷ & 0 & y & ∞ \\ 0 & 0 & 0 & ⊥ & 0 & ⊥ & 0 & 0 \\ x & 0 & xy & ∞ & x & ∞ & x/y & 0 \\ ∞ & ⊥ & ∞ & ∞ & ∞ & ∞ & ∞ & ⊥ \end{matrix}

In these tables, x and y are finite non-zero values. The table for negation x ↦ −x ought to be added to the above. But this table is rather trivial:

−x = x iff x ∈ {0, ∞, ⊥}.

There is no standard name for this ring-like algebraic structure ℂ ∪ {∞, ⊥}.

Chordal Metric. In order to avoid any special role for ∞ among the extended complex numbers, we introduce a natural metric on ℂ̂ via the stereographic projection σ : ℂ̂ → S^{2} where S^{2} ⊆ ℝ^{3} is the unit sphere centered at the origin of an Euclidean 3-space and ℂ is identified with the xy-plane. S^{2} is called the Riemann sphere, with North and South poles given by N = (0, 0, 1) and S = (0, 0, −1), respectively. The complex number p = p_{x} + ip_{y} (by identification with the point p = (p_{x}, p_{y}, 0) on the xy-plane) is mapped to the unique point σ(p) ∈ S^{2} such that N, p, σ(p) are collinear. We further define σ(∞) = N. This map can be explicitly given by

σ(p) = (\frac{2p_{x}}{|p|^{2} + 1}, \frac{2p_{y}}{|p|^{2} + 1}, \frac{|p|^{2} − 1}{|p|^{2} + 1}) , |p|^{2} = p_{x}^{2} + p_{y}^{2}.

The chordal distance Δ(p, q) between two points p, q ∈ ℂ̂ is equal to the Euclidean distance between σ(p) and σ(q). More explicitly,

Δ(p, q) = \{ \begin{matrix}\frac{2|p−q|}{\sqrt{(1+|p|^{2})(1+|q|^{2})}} & if p, q ≠ ∞, \\ \frac{2|p|}{\sqrt{1+|p|^{2}}} & if q = ∞. \end{matrix}

Note that Δ(p, q) ≤ 2.

Our applications in continued fractions focus on the restriction of this map (still called σ) to the extended real numbers

σ : ℝ̂ → S^{1}  (1)

where S^{1} is intersection of S^{2} with the xz-plane. We may also identify the xz-plane with ℂ and call S^{1} the “unit complex circle”. Under this identification, the North and South Pole of S^{1} are the complex numbers i and −i. See figure 1.

z  σ(1) = 1  x θ σ(0) = −i σ(−1) = −1  σ(r) σ(∞) = i 0  r

Figure 1: Stereographic projection: r ↦ σ(r) ∈ S^{1}.

Then σ(1) = 1, σ(−1) = −1, σ(0) = −i and σ(∞) = i. The inverse of σ is given by

σ^{−1}(e^{iθ}) = \frac{cos θ}{1 − sin θ} .

It is easy to see that Δ(0, 1) = \sqrt{2} and Δ(\sqrt{3}, ∞) = 1. More generally, Δ(0, r) = 2|r|/\sqrt{1 + r^{2}}, Δ(∞, r) = 2/\sqrt{1 + r^{2}}.

§3. General Terminology  Lecture XIV  Page 5

Exercises

Exercise 2.1:

(i) Verify the formulas for σ(p) and Δ(p, q).

(ii) Verify that Δ(p, q) is a metric. □

§3. General Terminology

Formally, a continued fraction is a possibly infinite expression of the form

q_{0} + \frac{p_{1}}{q_{1} + _{\frac{p_{2}}{q_{2}+_{\frac{p_{3}}{q_{3}+ \frac{p_{4}}{q_{4}+···}}}}}}  (2)

where p_{i}, q_{i} are extended complex numbers or functions of complex variables. We call p_{i}, q_{i} the ith partial numerator and ith partial denominator; p_{i}/q_{i} is the ith partial quotient. We refer to the partial numerators and partial denominators as terms of the continued fraction. For simplicity, we normally assume each q_{i} ≠ 0. To avoid the cumbersome form (2), we express the same continued fraction using a linear notation

q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} \frac{p_{3}}{q_{3}+} ⋯  (3)

or a summation-like notation

q_{0} + K_{i=1}^{B} (\frac{p_{i}}{q_{i}} )

where B ≥ 0 is an integer or ∞. The latter form is useful for stating explicit expressions for the general i-th partial denominator and numerator. For example,

ln(1 + z) = \frac{z}{1+} \frac{z/2}{1+} \frac{z/6}{1+} \frac{2z/6}{1+} \frac{2z/10}{1+} \frac{3z/10}{1+} \frac{3z/14}{1+} ⋯
= K_{i≥1} (\frac{a_{i}z}{1} )

where a_{1} = 1 and for i ≥ 1, a_{2i} = \frac{i}{2(2i−1)} and a_{2i+1} = \frac{i}{2(2i+1)}. This continued fraction converges for all z ∈ ℂ except when z ∈ (−∞, −1], part of the negative x-axis. Many such continued fractions are known for common transcendental functions. See the Exercise for a continued fraction for e^{z}.

The continued fraction is called terminating or non-terminating according to whether or not it has infinitely many terms.^{1} The length of a terminating continued fraction is the largest n such that both the nth partial numerator and denominator are defined; the length is infinite in case of a non-terminating continued fraction.

We are mainly interested in the continued fraction (3) when all p_{i}, q_{i} are numbers: in which case we say the continued fraction is numerical; otherwise it is functional. A typical example of a functional continued fraction is where all the p_{i}, q_{i} depends on a single variable X. For instance, Euler shows that the power series c_{0} + c_{1}X + c_{2}X^{2} + ⋯ is “equivalent” to

c_{0} + \frac{c_{1}X}{1−} \frac{\frac{c_{2}}{c_{1}} X}{1 + \frac{c_{2}}{c_{1}} X−} \frac{\frac{c_{3}}{c_{2}} X}{1 + \frac{c_{3}}{c_{2}} X−} ⋯ \frac{\frac{c_{n}}{c_{n−1}} X}{1 + \frac{c_{n}}{c_{n−1}} X−} ⋯

1Terminating/non-terminating continued fractions are also called finite/infinite in the literature. We avoid this terminology since “finite” and “infinite” also applies to extended numbers.

in a suitable sense (cf. below). Note that we write

⋯ \frac{p_{i}}{q_{i}−} \frac{p_{i+1}}{q_{i+1}+} ⋯

as an alternate form for

⋯ \frac{p_{i}}{q_{i}+} \frac{−p_{i+1}}{q_{i+1}+} ⋯

We now define the value of a continued fraction. This value is an element of ℂ̂ ∪ {⊥} when the continued function is numerical; otherwise the value is a function. We will not discuss the value of a functional continued fraction except to say that it is somewhat like the convergence of series, but more subtle (Exercise). When the continued fraction is numerical and terminating, the value is defined in an obvious fashion. For instance, the value of 1 + \frac{1}{2+} \frac{1}{2} is 7/5. For the value of a non-terminating continued fraction, we proceed as follows: if i ≥ 0 is at most the length of the continued fraction (3), we call the terminating continued fraction

q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} ⋯ \frac{p_{i−1}}{q_{i−1}+} \frac{p_{i}}{q_{i}}

the ith convergent of the continued fraction (3). The value of the ith convergent is called the ith quotient or ith approximant. For example, the ith quotient of (3) for i = 0, …, 4 are:

q_{0}, \frac{p_{1} + q_{0}q_{1}}{q_{1}} , \frac{p_{1}q_{2} + p_{2}q_{0} + q_{0}q_{1}q_{2}}{p_{1} + q_{1}q_{2}} ,  (4)
\frac{p_{1}p_{3} + p_{1}q_{2}q_{3} + p_{2}q_{0}q_{3} + p_{3}q_{0}q_{1} + q_{0}q_{1}q_{2}q_{3}}{p_{2}q_{3} + p_{3}q_{1} + q_{1}q_{2}q_{3}} .  (5)

The ith quotient is clearly a fraction P_{i}/Q_{i} which could be infinite (P_{i} ≠ 0, Q_{i} = 0) or indefinite (P_{i} = Q_{i} = 0); otherwise the ith quotient is finite. We define the value of a non-terminating continued fraction (3) to be the extended number r provided all but a finite number of its quotients are definite, and the sequence of definite quotients P_{i}/Q_{i} converges to r as i → ∞. Note that r may be ∞. A basic problem in the theory of continued fraction is to study conditions on p_{i}, q_{i} to ensure convergence. We prove such a theorem in §6.

We now define the (nominal) numerator and denominator of the ith quotient P_{i}/Q_{i}. The definition should not be taken for granted since there can be accidental cancellations between the nominal numerators and denominators^{2}. It is best to view them as polynomials in the partial numerators and denominators p_{j}, q_{j} (j ≤ i),

P_{i} = P_{i}(q_{0}, p_{1}, q_{1}, …, p_{n}, q_{n}),  Q_{n} = Q_{n}(p_{1}, q_{1}, …, p_{n}, q_{n}).  (6)

We call P_{i} and Q_{i} the ith numerator and ith denominator, respectively. They are defined as follows, using the compact matrix notation:

[ \begin{matrix}P_{−1} \\ Q_{−1} \end{matrix} ] := [ \begin{matrix}1 \\ 0 \end{matrix} ]  (7)
[ \begin{matrix}P_{0} \\ Q_{0} \end{matrix} ] := [ \begin{matrix}q_{0} \\ 1 \end{matrix} ]  (8)
[ \begin{matrix}P_{i} \\ Q_{i} \end{matrix} ] := [ \begin{matrix}P_{i−2} & P_{i−1} \\ Q_{i−2} & Q_{i−1} \end{matrix} ] [ \begin{matrix}p_{i} \\ q_{i} \end{matrix} ] , i ≥ 1  (9)

We must show that this definition is valid, i.e., P_{i}/Q_{i} gives the expected ith quotient. Clearly (9) is valid for i = 1 (we have concocted P_{−1}, Q_{−1} for this purpose). Assume inductively that P_{i}/Q_{i} gives the correct ith quotient. From (9) we get

2It turns out the systematic cancellation of common factors in the numerator and denominator cannot happen:

the polynomials P_{n}, Q_{n} that we define are absolutely irreducible in the indeterminates q_{0}, p_{1}, q_{1}, …, p_{n}, q_{n} (see [5]).

\frac{P_{i}}{Q_{i}} = \frac{p_{i}P_{i−2} + q_{i}P_{i−1}}{p_{i}Q_{i−2} + q_{i}Q_{i−1}} .  (10)

We observe that P_{i+1}/Q_{i+1} is obtained from P_{i}/Q_{i} by replacing q_{i} by q_{i} + \frac{p_{i+1}}{q_{i+1}} . Substituting in (10) we get

\frac{P_{i+1}}{Q_{i+1}} = \frac{p_{i}P_{i−2} + (q_{i} + \frac{p_{i+1}}{q_{i+1}} ) P_{i−1}}{p_{i}Q_{i−2} + (q_{i} + \frac{p_{i+1}}{q_{i+1}} ) Q_{i−1}}

= \frac{q_{i+1} (p_{i}P_{i−2} + q_{i}P_{i−1}) + p_{i+1}P_{i−1}}{q_{i+1} (p_{i}Q_{i−2} + q_{i}Q_{i−1}) + p_{i+1}Q_{i−1}}
= \frac{q_{i+1}P_{i} + p_{i+1}P_{i−1}}{q_{i+1}Q_{i} + p_{i+1}Q_{i−1}}

which proves that (9) is correct for i + 1.

Complements and Tails. The remaining terms of a continued fraction after we have extracted the ith convergent is

c_{i} = K_{j≥i+1} (\frac{p_{j}}{q_{j}} ) ,  (11)

which we will call the ith complement. Its value is called the complementary quotient. In general, a continued fraction (3) where the 0-th term vanishes (q_{0} = 0) is said to be in “complementary form”.

Sometimes we prefer to use an alternative decomposition of a continued fraction. The following continued fractions which comprise a prefix and a suffix of (3),

h_{i} = q_{0} + \frac{p_{1}}{q_{1}+} ⋯ \frac{p_{i−1}}{q_{i−1}+} \frac{p_{i}}{1} , t_{i} = q_{i} + K_{j≥i+1} (\frac{p_{j}}{q_{j}} )

are called (respectively) the ith head and tail of (3). The value (if it exists) of t_{i} is called the ith tail quotient.

Exercises

Exercise 3.1: Show that the ith quotients of

1 − \frac{1}{2−} \frac{1}{2−} \frac{1}{2−} ⋯

is \frac{1}{i+1} for all i ≥ 0. Hence the value is 0. □

Exercise 3.2: (Krishna-Rao) The continued fraction

1 + \frac{2}{3+} \frac{4}{5+} \frac{6}{7+} ⋯

has value 1/(\sqrt{e} − 1). □

§4. Ordinary Continued Fractions  Lecture XIV  Page 8

Exercise 3.3: (Lorentzen-Waadeland) The value of K_{i=1}^{∞} (\frac{6}{1}) is 2. HINT: the ith approximant is

−6\frac{(−3)^{i}−2^{i}}{(−3)^{i+1}−2^{i+1}} . □

Exercise 3.4: Consider the continued fraction

f(Z) = \frac{Z}{1 − Z+} \frac{Z}{1 − Z+} ⋯ = K (\frac{Z}{1 − Z} ) .

(i) f(Z) converges to Z if |Z| < 1. (ii) f(Z) converges to −1 if |Z| > 1. □

Exercise 3.5: Show that

(1 + X)^{r} = 1 + \frac{rX}{1−} \frac{\frac{r−1}{2}X}{1 + \frac{r−1}{2}X−} \frac{\frac{r−2}{3}X}{1 + \frac{r−2}{3}X−} ⋯

where the continued fraction terminates (with length r) if and only if r is a non-negative integer. □

Exercise 3.6: (Khovanskii)

(i) For any a, we have the functional continued fraction

\sqrt{X} = a + \frac{X − a^{2}}{2a+} \frac{X − a^{2}}{2a+} · · · .

(ii) The above continued fraction is convergent for all X ≥ 0. (iii) Show

\sqrt{Y^{2} + Z^{2}} = Y + \frac{Z^{2}}{2Y +} \frac{Z^{2}}{2Y +} \frac{Z^{2}}{2Y +} ⋯
= Y + \frac{Z^{2}}{Y + Z+} \frac{Y^{2}}{Y + Z+} \frac{Z^{2}}{Y + Z+} \frac{Y^{2}}{Y + Z+} ⋯
□

Exercise 3.7: Consider a continued fraction of the form

F (Z) = \frac{1}{b_{1} + Z−} \frac{a_{1}^{2}}{b_{2} + Z−} \frac{a_{2}^{2}}{b_{3} + Z−} · · · .

(i) Show that the nth denominator is given by

B_{n}(Z) = det [ \begin{matrix}b_{1} + Z & −a_{1} \\ −a_{1} & b_{2} + Z & −a_{2} \\ & −a_{2} & b_{3} + Z \\ & & & . & . & . \\ & & & & & & b_{n−1} + Z & −a_{n−1} \\ & & & & & & −a_{n−1} & b_{n} + Z \end{matrix} ] .

NOTE: Let B_{−1}(Z) = 0, B_{0}(Z) = 1 and a_{0} = 1. (ii) If the a_{i}, b_{i} are real then B_{n}(Z) has all real roots. □

§4. Ordinary Continued Fractions

Two continued fractions with the same value is said to be equivalent.^{3} It is important to study equivalent transformations of continued fractions, i.e., transformations that preserve values. The following is a simple example of an equivalent transformation of the continued fraction (3):

q_{0} + \frac{c_{1}p_{1}}{c_{1}q_{1}+} \frac{c_{1}c_{2}p_{2}}{c_{2}q_{2}+} \frac{c_{2}c_{3}p_{3}}{c_{3}q_{3}+} + ⋯ = q_{0} + K_{i=1}^{∞} \frac{c_{i−1}c_{i}p_{i}}{c_{i}q_{i}}  (12)

for non-zero c_{i}’s (c_{0} = 1). It is clear that the ith convergents of (12) and (3) are equal for all i. In general, when this condition holds between two continued fractions, we say that they are term-wise equivalent.

It is not hard to see that with suitable choice of c_{i}’s, every continued fraction (3) is term-wise equivalent to one whose partial numerators are 1:

q_{0} + \frac{1}{q_{1}+} \frac{1}{q_{2}+} \frac{1}{q_{3}+} · · · .  (13)

We call such^{4} a continued fraction (13) ordinary, and its value is given the compact notation

[q_{0}, q_{1}, q_{2}, …] = [q_{i}]_{i=0}^{∞}.  (14)

As examples we have \sqrt{2} = [1, 2, 2, 2, …], ∞ = [r, 0] (for any finite number r). The ith quotient of (14) is [q_{0}, q_{1}, q_{3}, …, q_{i}]; the ith tail and ith complementary quotients are [q_{i}, q_{i+1}, q_{i+2} …] and [0, q_{i}, q_{i+1}, q_{i+2} …] (respectively). Moreover,

[q_{0}, q_{1}, q_{2} …] = [q_{0}, q_{1}, …, q_{i−1}, [q_{i}, q_{i+1}, …] ].

If the partial denominators q_{i} (i ≥ 1) are positive integers in (13) and q_{0} is an integer, we call^{5} it a regular continued fraction.

Empty Ordinary Continued Fraction. It is convenient to introduce the empty ordinary continued fraction, denoted by the symbol []. We define the value of [] to be ∞ and its length is −∞. If n is the length of the continued fraction, we define its nth complement to be [] and so the nth complementary quotient is ∞.

Periodic Continued Fractions. If for some h ≥ 1 and n ≥ 0 we have

q_{i} = q_{i+h}

whenever i ≥ n, then we say (14) is periodic. This can be indicated either by an bar over the periodic part or by a semicolon separating the periodic part from a suffix:

[q_{0}, q_{1}, …, q_{n−1}, \overline{q_{n}, q_{n+1}, …, q_{n+h−1}}] or [q_{0}, q_{1}, …, q_{n−1}; q_{n}, q_{n+1}, …, q_{n+h−1}].  (15)

If h is chosen as small as possible, then h is called the period of the ordinary continued fraction. For instance \sqrt{2} = [1, 2, 2, \overline{2, 2, 2}] = [1, \overline{2}] = [1; 2] has period 1. The classic theorem about periodic continued fractions is due to Lagrange: the value of a real regular continued fraction is an irrational quadratic number if and only if the continued fraction is periodic. An irrational quadratic number has the form a + b\sqrt{d} where a, b are rational numbers, b ≠ 0 and d > 1 is squarefree. (One direction of this result is easy – see Exercise.) Unfortunately there is no known extension of Lagrange’s characterization to higher degree algebraic numbers.

3The more usual definition of “equivalence”, following L. Seidel (1855), corresponds to what we call term-wise equivalence.

4Lagrange concludes from this that there is no interest in the more general form of continued fractions; this is unwarranted for many reasons.

5Also called simple continued fraction, but we follow Perron [10] who uses regelmäßig.

The Continued Fraction Algorithm. It is clear that for any finite real number r we can define a regular continued fraction RCF(r) as follows: if r is an integer, then RCF(r) = r. Otherwise,

RCF(r) :=⌊r⌋ + \frac{1}{RCF(1/(r − ⌊r⌋))}.  (16)

This can be viewed as a process to transform a number into a sequence of integers and is sometimes called the “continued fraction algorithm”.

Is the representation of finite reals by regular continued fractions unique? The answer is no because of this easily seen identity:

[q_{0}, …, q_{n−1}, q_{n}, 1] = [q_{0}, …, q_{n−1}, q_{n} + 1], n ≥ 1

This identity implies that any terminating regular continued fraction is equivalent to one whose last partial quotient q_{n} is at least 2 whenever its length n is positive. It turns out that, with this sole exception, we have uniqueness:

Lemma 1

(i) There is bijective correspondence between the finite real numbers and regular continued fractions, provided we restrict the last partial quotient of a terminating continued fraction of positive length to be at least 2. (ii) Under the correspondence of part (i), a finite real number is irrational if and only its regular continued fraction is non-terminating.

We leave the proof as an Exercise. The distinction between a continued fraction and its value is often confused. The preceding lemma justifies the practice in case of regular continued fractions. We sometimes perpetrate the same language abusive by referring to the value “[q_{0}, q_{1}, q_{2}, …]” as a continued fraction.

Simple Operations on Ordinary Continued Fractions. For reciprocals, we have

\frac{1}{[q_{0}, q_{1}, …]} = \{ \begin{matrix}[0, q_{0}, q_{1}, …], & q_{0} > 0 \\ [q_{1}, q_{2}, q_{3}, …], & q_{0} = 0. \end{matrix}  (17)

For negation, we have −[q_{0}, q_{1}, q_{2}, …] = [−q_{0}, −q_{1}, −q_{2}, …] or more generally:

− [q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} ⋯] = [−q_{0} − \frac{p_{1}}{q_{1}−} \frac{p_{2}}{q_{2}−} ⋯] .  (18)

Alternatively, we can proceed as follows. It is easy to verify that

[x, y] = [x − 1, 1, −(y + 1)] or [x + 1, y − 1] = [x, 1, −y].  (19)

Applying this identity,

[−q_{0}, −q_{1}, −q_{2}, …] = [−q_{0}, −[q_{1}, q_{2}, …]]
= [−q_{0} − 1, 1, [q_{1}, q_{2}, …] − 1]
= [−q_{0} − 1, 1, [q_{1} − 1, q_{2}, …]]

This yields a negation formula that manipulates only a finite part of the original continued fraction.

−[q_{0}, q_{1}, q_{2}, q_{3}, …] = [−q_{0} − 1, 1, q_{1} − 1, q_{2}, q_{3}, …].  (20)

We can absorb partial quotients that vanish

[…, q_{n−1}, 0, q_{n+1}, …] = […, q_{n−1} + q_{n+1}, …],  n ≥ 1.  (21)

Using the identity (19), partial quotients of 1 can also be absorbed.

Finally, we defer the treatment of the arithmetic operations to a later section.

Exercise 4.1:

(i) Is the continued fraction

\frac{q_{0}q_{1} + p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} \frac{p_{3}}{q_{3}+} ⋯

equivalent to the (3)? (ii) What are the numerators and denominators of the continued fraction (12)? □

Exercise 4.2:

(i) What is the number [\overline{1}] = [1, 1, 1, …]? Likewise, [\overline{0}], [\overline{1, 2}] and [\overline{1, 2, 3}]? (ii) Give upper and lower bounds for [1, 2, 3, 4, …] = K_{i=1}^{∞} (\frac{1}{i}). Is this an algebraic number?

□

Exercise 4.3:

(i) The continued fraction solution to the equation X^{2} − 3X − 1 = 0 is X = [3, 3, 3, …] = [\overline{3}]. Use this to hand-compute arbitrarily good approximations to \sqrt{13}. HINT: what is the relation of X to \sqrt{13}? (ii) Show that \sqrt{13} = [3, \overline{1, 1, 1, 1, 6}]. □

Exercise 4.4: (Euler)

(i) For any numbers a, b, if X = a − \frac{b}{2} + \sqrt{1 + \frac{b^{2}}{4}} then

X − a = \frac{1}{b+} \frac{1}{b+} \frac{1}{b+} ⋯

(ii) Show that \sqrt{1 + a^{2}} = [a, 2a, 2a, …] = [a, \overline{2a}]. (This gives us the continued fractions of \sqrt{2}, \sqrt{5}, \sqrt{10}, etc.) □

Exercise 4.5: Let C = q′_{0} + \frac{p′_{1}}{q′_{1}+} \frac{p′_{2}}{q′_{2}+} ⋯ be the continued fraction equivalent to (3) such that the ith quotient P′_{i}/Q′_{i} of C is the (2i)th quotient of (3) for all i ≥ 0. Determine p′_{i}, q′_{i}. □

Exercise 4.6: Show the easy direction of Lagrange’s result characterizing irrational quadratic numbers, namely, if a real regular continued fraction is periodic, then its value is irrational quadratic. HINT: first assume the purely periodic case. [The other direction of Lagrange’s result is an exercise in §7.] □

Exercise 4.7: A real quadratic irrationality X = a + b\sqrt{d} is reduced if X > 1 and its conjugate X′ = a − b\sqrt{d} satisfies −1 < X′ < 0.

(i) Show that the regular continued fraction of a real quadratic irrationality is purely periodic if and only if it is reduced. (A regular continued fraction is purely periodic it has the form [\overline{q_{1}, …, q_{n}}]; the aperiodic part is empty.) (ii) If α = [\overline{q_{1}, q_{2}, …, q_{n}}] then the continued fraction of −1/α is [\overline{q_{n}, q_{n−1}, …, q_{1}}]. REMARK: see §8 for the general concept of a “reduced real irrationality”. □

§5. Möbius transformations  Lecture XIV  Page 12

Exercise 4.8: Show that

\sqrt{3} = 1 + \frac{2}{2+} \frac{2}{2+} \frac{2}{2+} · · · .

Apply the equivalent transformation (12) to convert this into the regular continued fraction \sqrt{3} = [1, \overline{1, 2}]. □

Exercise 4.9:

(i) Show that \sqrt{8} = [2, \overline{1, 4}]. More generally, \sqrt{4(1 + a^{2})} = [2a, \overline{a, 4a}]. (ii) Investigate the continued fractions of period 2: let X satisfy

X − a = \frac{1}{b+} \frac{1}{c+} \frac{1}{b+} \frac{1}{c+} ⋯ = \frac{1}{b+} \frac{1}{c + X − a}.

(iii) Conclude that \sqrt{a(a + 1)} = [a, \overline{2, 2a}]. (This gives the continued fraction of \sqrt{3}, \sqrt{6}, \sqrt{12}, etc.)

(d) Generalize this to \sqrt{a^{2} + b^{2}}. □

Exercise 4.10: Let x = \frac{1}{2}(\sqrt{5} − 1).

(i) Show that x = [0, \overline{1}]. (ii) If P_{i}/Q_{i} is the ith convergent to x, prove that

|\frac{P_{i}}{Q_{i}} − x| < \frac{1}{Q_{i}^{2}\sqrt{5}}.

(iii) Prove that the constant \sqrt{5} in the left-hand side cannot be improved for this choice of x. REMARK: for every irrational x there are infinitely many choices of p, q such that |\frac{p}{q} − x| < (q^{2}\sqrt{5})^{−1}. □

Exercise 4.11: (Euler) Consider the connection between power series and continued fractions: (i) The power series c_{0} + c_{1} + c_{2} + ⋯ (c_{i} ≠ 0 for i ≥ 1) and the continued fraction

c_{0} + \frac{c_{1}}{1−} \frac{c_{2}/c_{1}}{1 + (c_{2}/c_{1})−} \frac{c_{3}/c_{2}}{1 + (c_{3}/c_{2})−} ⋯ = K_{i≥1} (\frac{−c_{i}/c_{i−1}}{1 + (c_{i}/c_{i−1})})

have the same value. (ii) Show that for all real or complex x,

e^{x} = 1 + \frac{x}{1−} \frac{x/2}{1 + x/2−} \frac{x/3}{1 + x/3−} ⋯
= 1 + \frac{x}{1−} \frac{1.x}{2 + x−} \frac{2.x}{3 + x−} \frac{3.x}{4 + x−} \frac{4.x}{5 + x−} ⋯

HINT: put c_{i} = 1/i! in part (i). □

§5. Continued fractions as Möbius transformations

We now view continued fractions as transformations on the extended complex numbers ℂ̂ = ℂ∪{∞}. A Möbius transformation is a function f : ℂ̂ → ℂ̂ given by

f(z) = \frac{az + b}{cz + d}

where a, b, c, d are finite complex numbers.^{6} It is easy to check that f(z) is a constant function iff ad − bc = 0. The constant function is f(z) = b/d = a/c. We call ad − bc the determinant of f(z). Another special case is when f(z) = z (the identity function). This happens iff b = c = 0 and a = d. To avoid special cases, we henceforth restrict f to be neither a constant function nor the identity function. Since the function is unchanged if we multiply all of a, b, c, d by a common nonzero constant, we further assume

ad − bc = 1.

The reader can check that f(∞) = a/c and f(−d/c) = ∞. This function is analytic everywhere except for a pole at z = −d/c. The function is injective since

f(z) − f(y) = \frac{(ad − bc)(z − y)}{(cz + d)(cy + d)}

is zero if and only if z = y. It is surjective since its inverse function

z = \frac{d · f(z) − b}{−c · f(z) + a}

is also a Möbius transformation. We leave as an exercise to show that Möbius transformations map circles onto circles (straight lines are special cases of circles that pass through ∞).

Matrix Representation. Basic manipulations and properties of continued fractions are easier to “see” when stated in the language of matrices. Each x ∈ ℂ̂ is non-uniquely represented in homogeneous coordinates by the 2-vector of the form

[ \begin{matrix}cx \\ c \end{matrix} ] ,

for each choice c ∈ ℂ − {0}. Conversely, any vector

[ \begin{matrix}x \\ y \end{matrix} ]

with x, y ∈ ℂ̂ represents the value x/y ∈ ℂ̂ ∪ {⊥}. If either x = y = 0 or x = y = ∞, then x/y = ⊥ and the vector is said to be indefinite. If the 2-vectors u, v represents the same value, we say they are proportional and we write

u :: v.

In matrix notation, the function f(z) = (az + b)/(cz + d) is represented by a 2 × 2 matrix [ \begin{matrix}a & b \\ c & d \end{matrix} ]

and function application translates into multiplying a 2-vector by such a matrix: if z = x/y then

[ \begin{matrix}f(z) \\ 1 \end{matrix} ] :: [ \begin{matrix}a & b \\ c & d \end{matrix} ] [ \begin{matrix}x \\ y \end{matrix} ] = [ \begin{matrix}ax + by \\ cx + dy \end{matrix} ] .

The composition of two Möbius transformation becomes multiplication of two such matrices.

Classification. We call z^{∗} ∈ ℂ̂ a fix-point of f(z) if f(z^{∗}) = z^{∗}. It is easy to see that Z = z^{∗} is a solution to the following equation:

cZ^{2} + (d − a)Z − b = 0.

Since f(z) is not the identity function, this equation does not identically vanish — this implies that there are at most two fixed points. In case c = 0, d = a, we must have b ≠ 0, so there are no fixed points. This corresponds to the translation f(z) = z + (b/d). We can classify Möbius transformations by their actions relative to fixed points. More precisely, their iterated action f^{(n)}(z) (n-fold application of f, as n → ∞) can either move any point z ∈ ℂ̂ towards a fixed point or away from it. For simplicity, assume c ≠ 0 so that f has two fixed points z_{1}, z_{2} (not necessarily distinct). The following occurs:

6Such transformations are also called linear fractional transformations or homographic functions.

• (Parabolic) There is only one distinct fixed point z_{1}. Then f^{(n)}(z) → z_{1} as n → ∞ for all z ∈ ℂ̂.

• (Elliptic) We have z_{1} ≠ z_{2} and |cz_{1} + d| = |cz_{2} + d|. Then f^{(n)}(z) diverges for all z ≠ z_{1}, z_{2}.

• (Loxodromic) We have z_{1} ≠ z_{2} and |cz_{1} + d| > |cz_{2} + d|. Then f^{(n)}(z) → z_{1} as n → ∞ for all z ≠ z_{2}.

Continued Fractions as Transformations. The pair p_{i}, q_{i} of partial numerator and denominator in the continued fraction

q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} \frac{p_{3}}{q_{3}+} ⋯  (22)

can be viewed as the Möbius transformation

x ↦ \frac{p_{i}}{q_{i} + x}.  (23)

In terms of matrix transformations, (23) becomes:

[ \begin{matrix}x \\ 1 \end{matrix} ] ↦ [ \begin{matrix}0 & p_{i} \\ 1 & q_{i} \end{matrix} ] [ \begin{matrix}x \\ 1 \end{matrix} ] = [ \begin{matrix}p_{i} \\ q_{i} + x \end{matrix} ] .

Hence we call a matrix of the form

[ \begin{matrix}0 & p \\ 1 & q \end{matrix} ]

a partial quotient matrix. Similarly, the partial denominator q_{0} corresponds to the matrix transformation

[ \begin{matrix}x \\ 1 \end{matrix} ] ↦ [ \begin{matrix}1 & q_{0} \\ 0 & 1 \end{matrix} ] [ \begin{matrix}x \\ 1 \end{matrix} ] = [ \begin{matrix}q_{0} + x \\ 1 \end{matrix} ] .

T (q) := [ \begin{matrix}1 & q \\ 0 & 1 \end{matrix} ] .

is called a translation matrix.

The ith quotient (i ≥ 0) of the continued fraction (22) corresponds to the matrix product

M_{i}:= [ \begin{matrix}1 & q_{0} \\ 0 & 1 \end{matrix} ] [ \begin{matrix}0 & p_{1} \\ 1 & q_{1} \end{matrix} ] [ \begin{matrix}0 & p_{2} \\ 1 & q_{2} \end{matrix} ] ⋯ [ \begin{matrix}0 & p_{i} \\ 1 & q_{i} \end{matrix} ] .  (24)

Call M_{i} the ith convergent matrix of the continued fraction. If the continued fraction (22) has finite length n, then M_{n} is the transformation matrix associated with the continued fraction; if the length is infinite, the transformation matrix will be an infinite product of matrices, viewed formally. It is immediate that

det M_{i} = (−1)^{i}p_{1}p_{2} ⋯ p_{i}.  (25)

The ith convergent matrix can be expressed in terms of the the jth numerators P_{j} and denominators Q_{j} (6). It is easy to verify (cf. (7–9)) that

M_{i} = [ \begin{matrix}P_{i−1} & P_{i} \\ Q_{i−1} & Q_{i} \end{matrix} ] .  (26)

Hence, we have the so-called determinant formula

P_{i−1}Q_{i} − P_{i}Q_{i−1} = (−1)^{i}p_{0}p_{1}p_{2} ⋯ p_{i}  (p_{0} = 1).  (27)

This matrix is associated to the Möbius transformation

f_{i}(z) = \frac{zP_{i} + P_{i−1}}{zQ_{i} + Q_{i−1}} .  (28)

Notice that this is the value of the continued fraction

q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} ⋯ \frac{p_{i}}{q_{i}+} \frac{1}{z}.

That is, we append (1/z) as the (i + 1)st partial quotient. The reason we use 1/z instead of z is because this form is convenient to specialize to ordinary continued fractions where p_{i+1} = 1. More explicitly, for ordinary continued fraction [q_{0}, q_{1}, q_{2}, …, , q_{i}] we have

f_{i}(z) = [q_{0}, q_{1}, q_{2}, …, , q_{i}, z] = \frac{zP_{i} + P_{i−1}}{zQ_{i} + Q_{i−1}} .

We shall call f_{i}(z) in equation (28) the z-value of the continued fraction

q_{0} + \frac{p_{1}}{q_{1}+} \frac{p_{2}}{q_{2}+} ⋯ \frac{p_{i}}{q_{i}} .

Our original definition of the “value” of a continued fraction corresponds to z = ∞. Thus, 0-value is P_{i−1}/Q_{i−1} and the ∞-value is the usual value P_{i}/Q_{i}. Suppose x_{i} denotes the (i−1)st complementary quotient of the continued fraction (3), and let x_{0} denote the value of the continued fraction. Then x_{0} = q_{0} + x_{1} = q_{0} + p_{1}/(q_{1} + x_{2}). In general,

[ \begin{matrix}x_{0} \\ 1 \end{matrix} ] = [ \begin{matrix}P_{i−1} & P_{i} \\ Q_{i−1} & Q_{i} \end{matrix} ] [ \begin{matrix}x_{i} \\ 1 \end{matrix} ] .  (29)

Inverting the matrix, we obtain:

[ \begin{matrix}x_{i} \\ 1 \end{matrix} ] = [ \begin{matrix}P_{i−1} & P_{i} \\ Q_{i−1} & Q_{i} \end{matrix} ]^{−1} [ \begin{matrix}x_{0} \\ 1 \end{matrix} ] = \frac{(−1)^{i}}{p_{1}p_{2} ⋯ p_{i}} [ \begin{matrix}Q_{i} & −P_{i} \\ −Q_{i−1} & P_{i−1} \end{matrix} ] [ \begin{matrix}x_{0} \\ 1 \end{matrix} ] .

Recurrence for Tail Quotients. We carry out a similar analysis for tail quotients. First, let

t_{i}:= q_{i} + \frac{p_{i+1}}{q_{i+1}+} \frac{p_{i+2}}{q_{i+2}+} ⋯

denote the ith tail quotient of (3). Then we have t_{i} = q_{i} + \frac{p_{i+1}}{t_{i+1}} for i ≥ 0. By telescopy,

[ \begin{matrix}t_{0} \\ 1 \end{matrix} ] = [ \begin{matrix}q_{0} & p_{1} \\ 1 & 0 \end{matrix} ] [ \begin{matrix}t_{1} \\ 1 \end{matrix} ]
= [ \begin{matrix}q_{0} & p_{1} \\ 1 & 0 \end{matrix} ] [ \begin{matrix}q_{1} & p_{2} \\ 1 & 0 \end{matrix} ] [ \begin{matrix}t_{2} \\ 1 \end{matrix} ]
⋮
= [ \begin{matrix}q_{0} & p_{1} \\ 1 & 0 \end{matrix} ] [ \begin{matrix}q_{1} & p_{2} \\ 1 & 0 \end{matrix} ] ⋯ [ \begin{matrix}q_{n−1} & p_{n} \\ 1 & 0 \end{matrix} ] [ \begin{matrix}t_{n} \\ 1 \end{matrix} ] .

Expressing this in analogy to (29):

[ \begin{matrix}t_{0} \\ 1 \end{matrix} ] = [ \begin{matrix}A_{n} & B_{n} \\ C_{n} & D_{n} \end{matrix} ] [ \begin{matrix}t_{n} \\ 1 \end{matrix} ] .  (30)

where A_{n}, B_{n}, C_{n}, D_{n} are the analogues of P_{n}, Q_{n}, satisfying the recurrence relations:

[ \begin{matrix}A_{1} & B_{1} \\ C_{1} & D_{1} \end{matrix} ] = [ \begin{matrix}q_{0} & p_{1} \\ 1 & 0 \end{matrix} ] ,
[ \begin{matrix}A_{n+1} & B_{n+1} \\ C_{n+1} & D_{n+1} \end{matrix} ] = [ \begin{matrix}A_{n} & B_{n} \\ C_{n} & D_{n} \end{matrix} ] [ \begin{matrix}q_{n} & p_{n+1} \\ 1 & 0 \end{matrix} ] ,
= [ \begin{matrix}q_{n}A_{n} + B_{n} & p_{n+1}A_{n} \\ q_{n}C_{n} + D_{n} & p_{n+1}C_{n} \end{matrix} ] .  (31)

Notice that the recurrence for complementary quotients requires only 2 recurrence sequences (for P_{i}, Q_{i}) instead of 4 (for A_{i}, B_{i}, C_{i}, D_{i}). However, if we assume ordinary continued fractions (p_{i} = 1) then we have

B_{i} = A_{i−1},  D_{i} = C_{i−1},  (32)

with A_{0} = 1 and C_{0} = 0. But A_{i}, B_{i} is now related to the numerators and denominators:

A_{i+1} = P_{i},  C_{i+1} = Q_{i},  (i ≥ 0).  (33)

Inverting the matrices,

[ \begin{matrix}t_{n} \\ 1 \end{matrix} ] = (∏_{i=1}^{n} \frac{1}{p_{i}} ) [ \begin{matrix}0 & p_{n} \\ 1 & −q_{n−1} \end{matrix} ] ⋯ [ \begin{matrix}0 & p_{2} \\ 1 & −q_{1} \end{matrix} ] [ \begin{matrix}0 & p_{1} \\ 1 & −q_{0} \end{matrix} ] [ \begin{matrix}t_{0} \\ 1 \end{matrix} ]

= \frac{(−1)^{i}}{p_{1}p_{2} ⋯ p_{i}} [ \begin{matrix}D_{n} & −B_{n} \\ −C_{n} & A_{n} \end{matrix} ] [ \begin{matrix}t_{0} \\ 1 \end{matrix} ] .

Beardon [1] gives a general account of Möbius transformations (in any dimension).

Exercises

Exercise 5.1: Show that Möbius transformations map circles in the complex plane into circles. (i) Show that the equation of a circle is

Az\overline{z} + Bz + \overline{B}\overline{z} + C = 0

for complex constants A, B, C with A, C real. Also, the circle is a straight line iff A = 0. (ii) Show that if z = f(w) = (aw + b)/(cw + d), then the w satisfies another equation of the form

A′w\overline{w} + B′w + \overline{B′}\overline{w} + C′ = 0

for some other A′, B′, C′ with A′, C′ real. □

Exercise 5.2: Verify the three-fold classification of Möbius transformations and associated properties. □

Exercise 5.3: Consider the following matrix representation of a continued fraction of a\sqrt{2} (for any a), corresponding to a · [1, \overline{2}]

[ \begin{matrix}a & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}0 & 1 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}0 & 1 \\ 1 & 2 \end{matrix} ] · · · .

§6. Convergence Properties  Lecture XIV  Page 17

Show that if the ith convergent matrix M_{i} = [ \begin{matrix}a_{i} & a_{i+1} \\ b_{i} & b_{i+1} \end{matrix} ] then

a_{i} = \frac{a}{2} ((1 + \sqrt{2})^{i} + (1 − \sqrt{2})^{i}) , b_{i} = \frac{1}{2\sqrt{2}} ((1 + \sqrt{2})^{i} − (1 − \sqrt{2})^{i}) .

□

Exercise 5.4: Say two numbers x, y are “equivalent” if are related by an integer unimodular transformation: y = \frac{ax+b}{cx+d} where a, b, c, d are integers and ad − bc = ±1. Check that this is a mathematical equivalence.

(i) Any two rational numbers are equivalent.

(ii) If x, y are irrational then they are equivalent iff their regular continued fractions share a common suffix: x = [a_{0}, a_{1}, …] and y = [b_{0}, b_{1}, …] implies there exists k, ℓ such that for all i ≥ 0, a_{i+k} = bi + ℓ. (iii) Partition the following numbers according to their equivalence classes:

\sqrt{2}, \sqrt{3}, \sqrt{5}, (1 + \sqrt{5})/2, 1 + \sqrt{2}, 1 + \sqrt{3}.
□

§6. Convergence Properties

We investigate the ith numerator P_{i} and denominator Q_{i}. From (7–9), we get

[ \begin{matrix}P_{0} \\ Q_{0} \end{matrix} ] = [ \begin{matrix}q_{0} \\ 1 \end{matrix} ] ,  (34)
[ \begin{matrix}P_{1} \\ Q_{1} \end{matrix} ] = [ \begin{matrix}p_{1} + q_{0}q_{1} \\ q_{1} \end{matrix} ] ,  (35)
[ \begin{matrix}P_{2} \\ Q_{2} \end{matrix} ] = [ \begin{matrix}p_{1}q_{2} + q_{0}p_{2} + q_{0}q_{1}q_{2} \\ p_{1} + q_{1}q_{2} \end{matrix} ] ,  (36)
[ \begin{matrix}P_{3} \\ Q_{3} \end{matrix} ] = [ \begin{matrix}p_{1}p_{3} + p_{1}q_{2}q_{3} + q_{0}p_{2}q_{3} + q_{0}q_{1}p_{3} + q_{0}q_{1}q_{2}q_{3} \\ p_{2}q_{3} + q_{1}p_{3} + q_{1}q_{2}q_{3} \end{matrix} ] .  (37)

The polynomials P_{i}, Q_{i} are instances of an infinite family of polynomials K_{1}, K_{2}, … called continuant polynomials. We give a simple rule (cf. Knuth [8, p. 340]) to describe all the terms of P_{i}:

Lemma 2 Each term in P_{n} is obtained from the initial term q_{0}q_{1} ⋯ q_{n} by substituting zero or more non-overlapping pairs q_{i−1}q_{i} of consecutive variables by p_{i}. Moreover, every term obtained in this way appears in P_{n}

For instance, q_{0}p_{2}q_{3}q_{4}, q_{0}p_{2}p_{4} and p_{1}q_{2}p_{4} are terms in P_{4}. The proof is by a simple induction: the result is trivially true for P_{0} = q_{0} and P_{1} = p_{1} + q_{0}q_{1}. Inductively, the rule follows from the recurrence:

P_{n} = p_{n}P_{n−2} + q_{n}P_{n−1}.

An analogous rule for the terms in Q_{n} holds: we only have to use q_{1}q_{2} ⋯ q_{n} as initial term in the preceding lemma.

Define the polynomial K_{n} in 2n + 1 variables such that

K_{n} \binom{p_{1} p_{2} ⋯ p_{n}}{q_{0} q_{1} q_{2} ⋯ q_{n}}:= P_{n}(q_{0}, p_{1}, …, q_{n}).

Here we have arranged, following Muir (ca. 1874), the variables of K_{n} in a suggestive matrix form. With this notation, we see that

K_{n} \binom{p_{2} p_{3} ⋯ p_{n}}{q_{1} q_{2} q_{3} ⋯ q_{n}} = Q_{n}(q_{1}, p_{2}, …, q_{n}).

The continuant polynomials can also be written in a determinantal form (Exercise).

The difference between two consecutive quotients is easy to determine:

\frac{P_{i−1}}{Q_{i−1}} − \frac{P_{i}}{Q_{i}} = \frac{det M_{i}}{Q_{i−1}Q_{i}} = \frac{(−1)^{i}p_{1}p_{2} ⋯ p_{i}}{Q_{i−1}Q_{i}} .  (38)

In case of ordinary continued fractions, p_{j} = 1 for all j, and so

\frac{P_{i−1}}{Q_{i−1}} − \frac{P_{i}}{Q_{i}} = \frac{(−1)^{i}}{Q_{i−1}Q_{i}} .

If we telescope the difference (38) from i = 1 to n we obtain

\frac{P_{0}}{Q_{0}} − \frac{P_{n}}{Q_{n}} = \frac{−p_{1}}{Q_{0}Q_{1}} + \frac{p_{1}p_{2}}{Q_{1}Q_{2}} + ⋯ + \frac{(−1)^{n}p_{1}p_{2} ⋯ p_{n}}{Q_{n−1}Q_{n}}
\frac{P_{n}}{Q_{n}} = q_{0} + \frac{p_{1}}{q_{1}} − \frac{p_{1}p_{2}}{Q_{1}Q_{2}} + ⋯ + \frac{(−1)^{n+1}p_{1}p_{2} ⋯ p_{n}}{Q_{n−1}Q_{n}}

Next observe that the difference between the nth and n − 2nd quotients is

\frac{P_{n}}{Q_{n}} − \frac{P_{n−2}}{Q_{n−2}} = (−1)^{n} \frac{p_{1} ⋯ p_{n−1}}{Q_{n−2}Q_{n−1}} + (−1)^{n+1} \frac{p_{1} ⋯ p_{n}}{Q_{n−1}Q_{n}}
= (−1)^{n} \frac{p_{1} ⋯ p_{n−1}}{Q_{n−1}} (\frac{1}{Q_{n−2}} − \frac{p_{n}}{Q_{n}} )
= (−1)^{n} \frac{p_{1} ⋯ p_{n−1}q_{n}}{Q_{n−2}Q_{n}}  (39)

These lead to:

Theorem 3 Assume the partial numerators p_{i} and denominators q_{i} are positive for i ≥ 1 in the continued fraction (3).

(i) The sequence of quotients with even indices

\frac{P_{0}}{Q_{0}} , \frac{P_{2}}{Q_{2}} , \frac{P_{4}}{Q_{4}} , …,

are increasing but bounded above by q_{0} + \frac{p_{1}}{q_{1}} , and hence has a limiting value K_{e}. (ii) The sequence of quotients with odd indices

\frac{P_{1}}{Q_{1}} , \frac{P_{3}}{Q_{3}} , \frac{P_{5}}{Q_{5}} , …,

are decreasing but bounded below by q_{0}, and hence has a limiting value K_{o}. (iii) K_{e} ≤ K_{o}. (iv) (Seidel-Stern) In case each p_{i} = 1, then the divergence of the series ∑_{i=1}^{∞} q_{i} is a necessary and sufficient condition for K_{e} = K_{o} (= value of the continued fraction).

Proof. From equation (38), we have

\frac{P_{2i}}{Q_{2i}} < \frac{P_{2i−1}}{Q_{2i−1}} .

The inequality of part (iii) follows from this, assuming that K_{e} and K_{o} exist. From equation (39), we see that the sequence of even quotients is strict increasing, the sequence of odd quotients is strict decreasing. It follows that each P_{i}/Q_{i} (i ≥ 2) is greater than q_{0}: this is immediate if i is even; otherwise we have P_{i}/Q_{i} > P_{i−1}/Q_{i−1} > q_{0}. Likewise, P_{i}/Q_{i} is smaller than q_{0} + \frac{p_{1}}{q_{1}} . This proves parts (i) and (ii).

It remains to prove (iv). First assume that the series ∑_{i=1}^{∞} q_{i} is divergent and we will show that K_{e} = K_{o}. First observe that Q_{1} = q_{1}, Q_{2} = q_{1}q_{2} + 1 and

Q_{2n} = q_{2n}Q_{2n−1} + Q_{2n−2}, Q_{2n+1} = q_{2n+1}Q_{2n} + Q_{2n−1} (n ≥ 1)

imply Q_{2n} ≥ 1 and Q_{2n+1} ≥ q_{1} for all n ≥ 1. From this we get that

Q_{2n} ≥ q_{2n}q_{1} + Q_{2n−2}
≥ ⋯
≥ q_{2n}q_{1} + q_{2n−2}q_{1} + ⋯ + q_{4}q_{1} + q_{2}q_{1}.

Similarly

Q_{2n+1} ≥ q_{2n+1} + Q_{2n}
≥ ⋯
≥ q_{2n+1} + q_{2n−1} + ⋯ + q_{3} + q_{1}.

Thus, the divergence of ∑_{i=1}^{∞} q_{i} implies the divergence of either the odd Q-sequence Q_{1}, Q_{3}, Q_{5}, …, or the even Q-sequence Q_{2}, Q_{2}, Q_{6}, . . .. Hence the sequence Q_{1}Q_{2}, Q_{3}Q_{4}, Q_{5}Q_{6}, … diverges. The fact that K_{e} = K_{o} then follows from (38).

Conversely, if the series ∑_{i=1}^{∞} q_{i} is convergent, we show that K_{e} < K_{o}. First we show that the even P -sequence

P_{0}, P_{2}, P_{4}, …, P_{2n}, …,

and odd P -sequence

P_{1}, P_{3}, P_{5}, …, P_{2n+1}, …,

both converge to some values P_{∗} and P^{∗}, respectively. It is not hard to show by induction from P_{n} = q_{n}P_{n−1} + P_{n−2} that

P_{n} < ∏_{i=1}^{n}(1 + q_{i})

and hence

P_{n} < exp(∑_{i=1}^{n} q_{i}) < c_{0}

for some constant c_{0}. Next, by recursively expanding the term P_{n−2} in P_{n} = q_{n}P_{n−1} + P_{n−2}, we get

P_{n} = q_{n}P_{n−1} + q_{n−2}P_{n−3} + q_{n−4}P_{n−5} + · · · .

Hence

P_{n+2m} − P_{n} = q_{n+2m}P_{n+2m−1} + q_{n+2m−2}P_{n+2m−3} + ⋯ + q_{n+2}P_{n+1}
< c_{0}(q_{n+2m} + q_{n+2m−2} + ⋯ + q_{n+2}).

The convergence criterion of Bolzano-Cauchy for the series ∑_{i=1}^{∞} q_{i} says that the sequence is convergent if and only if for any ϵ > 0 there is a N such that for all m ≥ n ≥ N, q_{n} + q_{n+1} + ⋯ + q_{m} < ϵ. So for any ϵ > 0, for sufficiently large n, the above derivation implies P_{n+2m} − P_{n} < ϵ. Another application of the Bolzano-Cauchy criterion shows that the even and the odd P -sequences each converges. A similar argument shows that the even and odd Q-sequences converge to some values Q_{∗} and Q^{∗} respectively. Using the fact that P_{2n+1}Q_{2n} − P_{2n}Q_{2n+1} = 1, we conclude that in the limit

P^{∗}Q_{∗} − P_{∗}Q^{∗} = 1.

But K_{e} = P_{∗}/Q_{∗} and K_{o} = P^{∗}/Q^{∗}. This shows K_{o} − K_{e} = (Q_{∗}Q^{∗})^{−1} or K_{e} < K_{o} as desired.

Q.E.D.

Another classic convergence theorem (from Śleszyński-Pringsheim) is this: if |q_{i}| ≥ 1 + |p_{i}| for all i then K_{i≥1}(p_{i}/q_{i}) converges to a value of modulus ≤ 1.

Approximation of Irrationals by Rationals. The preceding shows that the value K (if it exists) of the continued fraction (3) is equal to the series

K = q_{0} + ∑_{i≥1}(−1)^{i+1} \frac{p_{1} ⋯ p_{i}}{Q_{i−1}Q_{i}} .

Moreover, for each n ≥ 2, it satisfies

|K − \frac{P_{n}}{Q_{n}} | < |\frac{p_{1} ⋯ p_{n}}{Q_{n−1}Q_{n}} | .

In particular, the nth approximant of the regular continued fraction of any K satisfies

|K − \frac{P_{n}}{Q_{n}} | ≤ \frac{1}{Q_{n−1}Q_{n}} < \frac{1}{c_{0}Q_{n}^{2}}  (40)

where c_{0} = 1. It can be shown that for any two consecutive quotients of K, one of them satisfies the inequality with c_{0} = 2. It may seem surprising that this turns out to be the defining characteristic of quotients: whenever any fraction p/q has the property |K − p/q| < 1/(2q^{2}), then p/q is a quotient of the regular continued fraction of K. A theorem of Borel says that of any three consecutive quotients, at least one satisfies the above inequality with c_{0} = \sqrt{5}. Hence every irrational number K has infinitely many approximations P_{n}/Q_{n} satisfying the above inequality with c_{0} = \sqrt{5}. This is the best possible in the sense that the statement fails if any larger value of c_{0} is used.

Exercises

Exercise 6.1: Prove that the following problem can be solved in polynomial time in the bit-sizes of integer N > 1 and of the rational number α: given N, α, find a rational number p/q such that |qα − p| is minimum, subject to q ≤ N. □

Exercise 6.2: Show that

P_{n} = det ( \begin{matrix}q_{0} & −1 & & & & & & 0 \\ p_{1} & q_{1} & −1 & & & & & 0 \\ 0 & p_{2} & q_{2} & −1 & & & & 0 \\ 0 & & p_{3} & q_{3} & −1 & & & 0 \\ & & & & & ⋯ \\ 0 & & & & & p_{n−1} & q_{n−1} & −1 \\ 0 & & & & & & p_{n} & q_{n} \end{matrix} ) .

§7. Real Möbius Transformation  Lecture XIV  Page 21

HINT:

−P_{0}  = −q_{0},
q_{1}P_{0} −P_{1}  = −p_{1},
p_{2}P_{0} q_{2}P_{1} −P_{2}  = 0,
p_{3}P_{1} q_{3}P_{2} −P_{3}  = 0,
⋯
p_{n−1}P_{n−3} q_{n−1}P_{n−2} −P_{n−1}  = 0,
p_{n}P_{n−2} q_{n}P_{n−1} −P_{n} = 0

(b) Derive a similar determinantal form for Q_{n}.

(c) Conclude that

Q_{n} = \frac{∂P_{n}}{∂q_{0}}

and

K_{n} \binom{p_{1} p_{2} ⋯ p_{n}}{q_{0} q_{1} q_{2} ⋯ q_{n}} = K_{n} \binom{p_{n} p_{n−1} ⋯ p_{1}}{q_{n} q_{n−1} q_{n−2} ⋯ q_{0}}

□

Exercise 6.3: (Gosper) Give a method to compute the rational number with minimum denominator that lies within an interval [a, b] with rational endpoints. □

§7. Real Möbius Transformation

We consider the method of Lagrange and Vincent for computing the regular continued fraction of a real algebraic number. For modern updates on this method see [14] and Cantor, Galyean and Zimmer [3]. Thull reports that his implementation of this approach is faster than Newton’s method by a factor of 3 to 4.

For this and the next section, assume α_{0} is a real root of a real polynomial A_{0}(X) of degree m ≥ 2. We may assume that A_{0}(X) has only simple non-integer roots, and we are given an isolating interval [r_{0}, s_{0}] with rational endpoints for α_{0}. Our goal is to compute the regular continued fraction of α_{0}.

The basic method is simple to understand. By binary search, we can compute a_{0} = ⌊α_{0}⌋, viz., a_{0} is the unique integer n between ⌊r_{0}⌋ and ⌊s_{0}⌋ such that A_{0}(n)A_{0}(n + 1) < 0. Then we could output a_{0} as the zeroth partial denominator q_{0}. We then transform α_{0} to α_{1} = \frac{1}{α_{0}−a_{0}} . Notice that α_{1} is the root of the transformed polynomial

A_{1}(X) = X^{m}A_{0}(a_{0} + \frac{1}{X}).

The “key question” for continuing this process is to find a simple rule for a new isolating interval [r_{1}, s_{1}] of α_{1} relative to A_{1}(X). If so, we can repeat this process indefinitely: find a_{1} = ⌊α_{1}⌋, transform A_{1}(X) to A_{2}(X) and find an isolating interval for α_{2} := \frac{1}{α_{1}−a_{2}} , etc. We refer to this generic process as the “continued fraction algorithm for (real) roots”.

Transformations of the Complex Plane. To answer the “key question”, we study the effects of the map

T_{0}(z) = a_{0} + (1/z)  (41)

on the complex plane, corresponding to egesting the term a_{0} or to the equation α_{0} = a_{0} + (1/α_{1}) = T_{0}(α_{1}). In general, if the regular continued fraction of α_{0} is [a_{0}, a_{1}, …], then after egesting n + 1 partial denominators, we have the Möbius transformation (see equation (30))

T_{n} : z ↦ [a_{0}, a_{1}, …, a_{n}, z] = \frac{zA_{n+1} + A_{n}}{zC_{n+1} + C_{n}} = \frac{zP_{n} + P_{n−1}}{zQ_{n} + Q_{n−1}}

where A_{i}, C_{i}, P_{i}, Q_{i} are given by equations (31), (32) and (33) (with a_{i}’s in place of q_{i}’s). Note that P_{n}, Q_{n} are positive integers such that for n ≥ 2,

P_{n} ≥ max{P_{n−1}, Q_{n}} ≥ min{P_{n−1}, Q_{n}} ≥ Q_{n−1} ≥ 0.

The first and last inequality is strict for n ≥ 3. More generally, consider the “positive” Möbius transformation T : z ↦ w = \frac{az+b}{cz+d}, or in matrix form

T : [ \begin{matrix}z \\ 1 \end{matrix} ] ↦ [ \begin{matrix}a & b \\ c & d \end{matrix} ] [ \begin{matrix}z \\ 1 \end{matrix} ] = [ \begin{matrix}w \\ 1 \end{matrix} ] ,  (42)

where a ≥ max{b, c} ≥ min{b, c} ≥ d ≥ 0 are reals and determinant

Δ = ad − bc ≠ 0.

We said (§5) that circles (in the z-plane) are transformed into circles (in the w-plane) by such transformations. Since T is real, we have T (\overline{z}) = \overline{T (z)} (\overline{z} denotes complex conjugation). This means that the real line is invariant under T and T has reflection symmetry about the real line. A simple calculation for the following 6 points shows

T (0) = \frac{b}{d}, T (1) = \frac{a + b}{c + d}, T (∞) = \frac{a}{c}, T (−d/c) = ∞, T (−b/a) = 0, T (−\frac{b + d}{a + c}) = −1.

See figure 2 for a representation of this mapping.

∞  (b + a)/(c + d) i  1  K_{T} K_{F}  −1 −b/a−1 −(b + d)/(a + c)  ∞  b/d Re(z) = −d/c  Re(w) = a/c 1  F = T^{−1} T 0  0  I z  w −i
Figure 2: Transformation T : z ↦ w = (az + b)/(cz + d), Δ < 0.

Let I_{T} be the interval on the real-axis of the w-plane with end-points a/c and b/d. It follows from the above calculations that T maps the imaginary axis of the z-plane to the circle K_{T} where K_{T} is the circle with diameter I_{T}. Note that \frac{a}{c} − \frac{b}{d} = \frac{Δ}{cd}. So a/c > b/d iff Δ > 0. Similarly −b/a > −d/c iff Δ > 0. Figure 2 illustrates the transformation for Δ < 0. Moreover, since the distinction between the inside and outside of a circle is preserved by Möbius transformations, and T (1) lies inside K_{T} while T (−d/c) lies outside K_{T}, we conclude that the entire half-plane Re(z) > 0 is mapped to the open disc inside K_{T}, and the positive real axis of the z-plane to I_{T}.

Similarly, let F denote the inverse of T, and I_{F} the interval on the real-axis of the z-plane with endpoints −b/a and −d/c, and K_{F} be the circle with diameter I_{F}. Then F maps K_{F} to the imaginary axis of the w-plane and I_{F} to the positive real axis of the w-plane.

Another notable feature is that the line Re(z) = −d/c is mapped into the line Re(w) = a/c. Summarizing these observations:

Lemma 4 The transformation T in (42) from the z-plane to the w-plane has these properties:

(i) The half-plane Re(z) > 0 is mapped to the open disc inside K_{T}, and Re(z) = 0 is mapped to the circle K_{T}. (ii) The circle K_{F} is mapped to the negative real axis in the w-plane and its interior is mapped to the half-plane Re(w) < 0. (iii) The half-plane Re(z) > −d/c is mapped to the half-plane Re(w) > a/c, and the line Re(z) = −d/c becomes the line Re(w) = a/c.

Now specialize our considerations to the case T = T_{0} as given by (41). The associated matrix is

[ \begin{matrix}a & b \\ c & d \end{matrix} ] = [ \begin{matrix}a_{0} & 1 \\ 1 & 0 \end{matrix} ] .

Let us assume a_{0} > 0. The circle K_{T} turns out to be the line Re(w) = a_{0}, and hence the half-plane Re(z) > 0 is simply translated to the half-plane Re(w) > a_{0}. In fact, parts (i) and (iii) in the lemma become identical. We can also verify that the half-plane Re(z) > 1 becomes the interior of the circle K_{a_{0}} with diameter [a_{0}, a_{0} + 1]. Furthermore, the real intervals [0, 1] and [∞, −1/a] in the z-plane transforms (respectively) into the real intervals [a_{0} + 1, ∞] and [0, a_{0}] in the w-plane. See figure 3.

.

Transformation of Isolating Intervals. Let us see how the roots of A_{0}(X) are transformed by T. Let its roots be

α_{0} = α^{(1)}, α^{(2)}, …, α^{(m)}.  (43)

Then

A_{1}(X) := A_{0}(T (X)).

is a real polynomial whose roots,

F (α_{0}^{(1)}), F (α^{(2)}), …, F (α^{(m)}),

are obtained by applying the inverse transform F := T^{−1} to the roots of A_{0}(X). Let us assume α_{0} > 0 and [r_{0}, s_{0}] ⊆ [0, ∞] is an isolating interval for α_{0} with respect to A_{0}(X), and let T = T_{0} be the transformation (41). Writing F_{0} := T_{0}^{−1} and α_{1} := F_{0}(α_{0}), and a_{0} = ⌊α_{0}⌋, it follows that

α_{1} ∈ F_{0}([a_{0}, a_{0} + 1]) = [1, ∞].

Notice that F_{0}([r_{0}, s_{0}]) is an isolating interval for α_{1} relative to A_{1}(X) = A_{0}(T_{0}(X)). A fortiori,

I_{1} := F_{0}([r_{0}, s_{0}]) ∩ [1, ∞]

§8. Continued Fraction of Roots  Lecture XIV  Page 24

i  1 −1 −1  a_{0} −1/(a_{0} + 1) −1/a_{0} K_{F}  a_{0} + 1 −i  K_{a_{0}} ∞  ∞ T_{0} 1  0 0  F_{0} = T_{0}^{−1} z  w
Figure 3: Transformation T_{0} : z ↦ (a_{0}z + 1)/z.

is an isolating interval for α_{1}. It is easy to see that I_{1} = [r_{1}, s_{1}] where

r_{1} := \{ \begin{matrix}F_{0}(s_{0}), & if s_{0} < a_{0} + 1, \\ 1, & else; \end{matrix}  (44)
s_{1} := \{ \begin{matrix}F_{0}(r_{0}), & if r_{0} > a_{0}, \\ ∞, & else, \end{matrix}

We have thus answered the “key question” that motivated this section.

We dispose of two final details: (a) We have assumed α_{0} > 0. The condition α_{i} > 0 is clearly maintained for i ≥ 1. In case α_{0} < 0, we can replace α_{0} by α_{0} − ⌊α_{0}⌋ before starting the initial iteration, and also modify A_{0}(X) and [r_{0}, s_{0}] accordingly. (b) If s_{1} = ∞, we may have trouble performing the standard binary search for a_{1} = ⌊α_{1}⌋ in the infinite interval [r_{1}, s_{1}]. But it is easy to replace s_{1} by some finite upper bound on α_{1} (for instance, Cauchy’s bound in §VI.2).

Exercises

Exercise 7.1: Let α = (−b + \sqrt{Δ})/2a be a zero of A(X) = aX^{2} + bX + c with discriminant Δ = b^{2} − 4ac.

(i) Let a_{0} = ⌊α⌋ and let α = a_{0} + (1/α′). Let α′ be a root of the polynomial a′X^{2} + b′X + c′. Show that b^{′2} − 4a′c′ = Δ. (ii) Let T be the transformation (42) and A(T (X)) = a^{T} X^{2} + b^{T} X + c^{T}. If α lies between a/c and b/d and |ad − bc| = 1 then |a^{T} | < 2|aα| + |a| + |b|, |c^{T} | < 2|aα| + |a| + |b| and |b^{T} | < 4(2|aα| + |a| + |b|)^{2} + |Δ|. (iii) Conclude that the regular continued fraction of a quadratic number is eventually periodic. (This is the harder direction of Lagrange’s theorem, §4). □

§8. Continued Fraction of Roots

Let us recapitulate the continued fraction algorithm developed in the previous section. Suppose we are given a polynomial A_{0}(X) of degree m and an isolating interval [r_{0}, s_{0}] for a real root α_{0} > 0 of A_{0}. To generate the regular continued fraction [a_{0}, a_{1}, a_{2}, …] of α, we compute the following successive members of the following sequence of tuples:

(r_{i}, s_{i}, A_{i}(X), a_{i}),  i ≥ 0  (45)

where

1. [r_{i}, s_{i}] is an isolating interval for a root α_{i} of A_{i}(X);

2. a_{i}:=⌊α_{i}⌋;

3. A_{i+1}(X) := X^{m}A_{i}(a_{i} + X^{−1}); and

4. r_{i} and s_{i} are computed as in equation (44); we assume that s_{i} is further replaced by some root-bound if this is better.

Here, α_{i} = 1/(α_{i−1} − a_{i−1}) is just the ith tail quotient of [a_{0}, a_{1}, a_{2}, …]. Note that a_{i} is found by a binary search on the interval [⌊r_{i}⌋, ⌊s_{i}⌋]

Although the sequence (45) is potentially infinite, it is useful to give a definite termination condition. Suppose that we only want to approximate α_{0} to within some absolute error ϵ > 0. Then we can compute, in addition to (45), also the ith numerator P_{i} and denominator Q_{i} (§3) of the [a_{0}, a_{1}, …]. We can terminate this computation at the ith iteration where

\frac{1}{Q_{i−1}Q_{i}} ≤ ϵ

since the ith approximant P_{i}/Q_{i} has the property |P_{i}/Q_{i} − α_{0}| < 1/(Q_{i−1}Q_{i}) (§6).

The reader can easily turn this description into a more explicit algorithm.

Reduced Numbers. We define a real algebraic number α to be reduced if α > 1 and all of whose conjugates β distinct from α lie in the interior of circle in the complex plane with the real line segment [−1, 0] as diameter. This is a variant of a notion of Zassenhaus (see [3]): a real algebraic number α is said to be in “reduced state” if α > 1 and for any conjugate β ≠ α,

Re(β) < 0, |β| < 1.

Clearly, our reduced numbers are in reduced state. It is also related to the concept of a PV-number^{7}. Notice that the transformation (42) is favorable for reduced numbers: if α_{0} is reduced then so is F (α_{0}). Indeed, our definition is motivated by these transformations, and it is in some sense the most natural from this view point. Reduced numbers have the trivial isolating interval [1, ∞], and the tails of their continued fractions remain reduced. We now show that every real algebraic number can be transformed into a reduced number within an explicitly given number of transformations of the form (41).

Let δ > 0 be a root separation bound (§VI.7) for A_{0}(X), and as usual, let α_{i} be the ith tail quotient of the regular continued fraction of α_{0}.

7A PV- or Pisot-Vijayaraghavan number is an algebraic integer α all of whose conjugates, excepting α itself, lies in the unit circle |z| < 1. See Cassels [4].

Theorem 5 If Q_{i−2}Q_{i−1} ≥ 2/δ then α_{i+2} is a reduced number.

Proof. Let β ≠ α_{0} be any conjugate of α_{0}. Setting β_{0} := β, we transform β_{i} to β_{i+1} = 1/(β_{i} − a_{i}), in analogy to our transformations on the α_{i}’s. Then we have, for i ≥ 1,

[ \begin{matrix}β \\ 1 \end{matrix} ] = [ \begin{matrix}P_{i} & P_{i−1} \\ Q_{i} & Q_{i−1} \end{matrix} ] [ \begin{matrix}β_{i} \\ 1 \end{matrix} ]
[ \begin{matrix}β_{i} \\ 1 \end{matrix} ] = (−1)^{i} [ \begin{matrix}Q_{i−1} & −P_{i−1} \\ −Q_{i} & P_{i} \end{matrix} ] [ \begin{matrix}β \\ 1 \end{matrix} ]
β_{i} = (−1)^{i} \frac{βQ_{i−1} − P_{i−1}}{−βQ_{i} + P_{i}}
= (−1)^{i} \frac{β − P_{i−1}/Q_{i−1}}{−β + P_{i}/Q_{i}} · \frac{Q_{i−1}}{Q_{i}}
= (−1)^{i} \frac{β − P_{i−1}/Q_{i−1}}{−β + P_{i}/Q_{i}} · \frac{1}{a_{i}} · (1 − \frac{Q_{i−2}}{Q_{i}} )  (46)

where the last equation is a consequence of the recurrence Q_{i} = a_{i}Q_{i−1} + Q_{i−2}. Our goal is to show that

|β_{i}| < 1/a_{i}  (47)

for i large enough. Once this goal is reached, all the conjugates of α_{i} lies in the half-plane Re(w) < 1 and by our observations on the map T_{0}, these conjugates will be mapped via F_{0} to the half-space Re(z) < 0. That is, all the conjugates of α_{i+1} (which are among the roots of A_{i+1}(X)) have negative real parts. By another application of the observation about T_{0}, we conclude that all the conjugates of α_{i+2} lies within the circle with diameter [−1, 0], i.e., α_{i+2} is reduced, proving our theorem.

The goal (47) follows from (46) if we show

|\frac{β − P_{i−1}/Q_{i−1}}{−β + P_{i}/Q_{i}} | ≤ 1 + \frac{Q_{i−2}}{Q_{i}} .  (48)

To this end, note that

|\frac{β − P_{i−1}/Q_{i−1}}{−β + P_{i}/Q_{i}} | = |\frac{β − (P_{i}/Q_{i}) − (−1)^{i}/(Q_{i}Q_{i−1})}{−β + (P_{i}/Q_{i})}|
≤ 1 + \frac{1}{Q_{i−1}Q_{i}} · \frac{1}{| − β + (P_{i}/Q_{i})|}.

Hence it suffices to show that

\frac{Q_{i−2}}{Q_{i−1}} ≥ \frac{1}{Q_{i−1}Q_{i}} \frac{1}{| − β + (P_{i}/Q_{i})|},
Q_{i−1}Q_{i−2} ≥ \frac{1}{| − β + (P_{i}/Q_{i})|}.  (49)

By definition of δ, |β − α_{0}| ≥ δ. From (40), |P_{i}/Q_{i} − α_{0}| ≤ 1/(Q_{i}Q_{i−1}). Hence, if i satisfies the condition of the theorem then

|−β + \frac{P_{i}}{Q_{i}} | ≥ |β − α_{0}| − |α_{0} − \frac{P_{i}}{Q_{i}} | ≥ δ − \frac{1}{Q_{i}Q_{i−1}} > \frac{δ}{2} ≥ \frac{1}{Q_{i−1}Q_{i−2}} .

Q.E.D.

A simplified version of this bound goes as follows. Recall that Q_{i}’s satisfies the recurrence

Q_{i} = a_{i}Q_{i−1} + Q_{i−2}, (i ≥ 2; Q_{0} = 1, Q_{1} = q_{1}).

Compare this with the Fibonacci numbers

F_{i} = F_{i−1} + F_{i−2}, (i ≥ 2; F_{0} = 0, F_{1} = 1).

It follows that

Q_{i} ≥ F_{i+1},  i ≥ 0.  (50)

It is easy to show that F_{i} ≤ ϕ^{i−1} for i ≥ 1 and ϕ = (\sqrt{5} − 1)/2. Thus Q_{i} ≥ ϕ^{i} for all i ≥ 0. So if 2i − 3 ≥ log_{ϕ}(2/δ), i.e.,

i ≥ \frac{3 + log_{ϕ}(2/δ)}{2},  (51)

then α_{i+2} will be reduced.

For the special case of quadratic numbers, more efficient and specialized algorithms for their continued fractions have been known from antiquity (Exercises).

Exercises

Exercise 8.1: Let R:={⌊r_{0}⌋, ⌊s_{1}⌋, ⌊r_{2}⌋, ⌊s_{3}⌋, …} and S:={⌊s_{0}⌋, ⌊r_{1}⌋, ⌊s_{2}⌋, ⌊r_{3}⌋, …}. Then both R and S eventually becomes the periodic sequence {…, 1, ∞, 1, ∞, …}. Before the appearance of this periodic part, R is the regular continued fraction expansion of r_{0} and S is the regular continued fraction expansion of s_{0}. The common “aperiodic” prefix of both sequences must agree except possibly for the last partial quotient. □

Exercise 8.2:

(i) Show that F_{i} = (ϕ^{n} − ϕ̂^{n})/\sqrt{5} where ϕ = (\sqrt{5} − 1)/2 and ϕ̂ = 1 − ϕ = −0.618 . . .. Verify the bound F_{i} ≥ ϕ^{i−1}. (ii) If A_{0}(X) is of degree m and ∥A_{0}∥_{∞} ≤ M, deduce an upper bound on i in terms of m, M that guarantees α_{i} will be reduced. □

Exercise 8.3: Let a_{0}, a_{1}, … be an arbitrary sequence of positive integers and we transform an initial real polynomial A_{0}(X) by a succession of substitutions, A_{i+1}(X) = A_{i}(a_{i} + X^{−1}). If i satisfies (51) then A_{i}(X) has at most one root with positive real part. NOTE: This is closely related to a theorem of Vincent (1836) which Uspensky [15] uses as a basis for a root separation method. Vincent’s theorem concludes that A_{i}(X) has at most one sign variation if i satisfies a comparable bound to (51). □

Exercise 8.4: (Thull) Suppose α_{0} is reduced and T (α_{1}) = α_{0} where T is given by (42). (i) Let S = α^{(2)} + ⋯ + α^{(m)} be the sum of all the conjugates of α_{0} which are different from α_{0}. Then S lies in the interval with endpoints −(m − 1)b/a and −(m − 1)d/c. (ii) Let A_{0}(T (X)) = ∑_{i=0}^{m} b_{i}X^{i}, where A_{0}(α_{0}) = 0. Then α_{1} lies in the interval with endpoints −(b_{m−1}/b_{m}) + (m − 1)b/a −(b_{m−1}/b_{m}) + (m − 1)d/c. □

Exercise 8.5: We develop an algorithm for quadratic numbers. Let N > 1 be a square-free integer, α = (a + \sqrt{N})/b for integers a, b and R = ⌊\sqrt{N}⌋.

(i) ⌊(a + \sqrt{N})/b⌋ is equal to ⌊(a + R)/b⌋ if b > 0 and equal to ⌊(1 + a + R)/b⌋ if b < 0. (ii) Let q = ⌊(a + R)/b⌋ and suppose (a′ + R)/b′ = ((a + R)/b − q)^{−1}. Then a′ = bq − a and b′ = (N − a^{′2})/b.

§9. Arithmetic Operations  Lecture XIV  Page 28

(iii) Repeating the transformations (a, b) → (a′, b′), let us form the sequence {(a_{i}, b_{i}) : i ≥ 0} where (a_{0}, b_{0}) = (a, b). Prove that for i large enough, |a_{i}| < R, |b_{i}| < 2R. [Hence it becomes periodic.] (iv) Develop a continued fraction algorithm of α using these facts (assuming that we can compute floor function).

(v) Show that α is reduced iff 0 < a < \sqrt{N} and \sqrt{N} − a < b < \sqrt{N} + a.

(vi) Modify your algorithm in (iii) to detect the onset of periodicity HINT: recall a characterization of reduced quadratic numbers in an exercise of §4. □

§9. Arithmetic Operations

We consider the arithmetic operations +, −, ×, ÷. The algorithmic idea is a very natural one. Say we want to compute x + y where x, y are continued fractions. The result z is supposed to be a continued fraction as well. The algorithm for z will request successive terms from x and y as needed. So we view a continued fraction x as a process that can respond to requests for its next term. Once x outputs a term, it transforms itself into a new process for a modified continued fraction x′. We assume that x′ has no memory of its previous outputs – so the algorithm for z must remember these outputs (in some form). Thus in general, a process has internal memory in the form of state variables. Similarly, the algorithm for adding x, y can be viewed as a process for z. The terms of a continued fraction q_{0} + K_{i≥1}(p_{i}/q_{i}) are given in the order q_{0}, p_{1}, q_{1}, p_{2}, q_{2}, . . .. As terms are ingested by the algorithm for x + y, the state variables of (the process) for z change. We have no á priori requirement on how terms from x or y are to be ingested – this is under the control of the algorithm for z. One obvious possibility is to ingest one term each from x and y simultaneously. We expect the algorithm to egest terms of z = x + y from time to time. These ideas fit very well into the concept of “streams” and “lazy evaluation” in the programming milieu. What we call a process can be identified as a stream. Lazy evaluation of z means that the algorithm ingests terms from x, y only when there is a pending request for a term of z. Of course, the stream for z can be fed into other on-going computation.

Following Gosper [2], the processes for arithmetic operations can unified under the process for computing the general function

z(x, y) = \frac{axy + bx + cy + d}{a′xy + b′x + c′y + d′}  (52)

where a, b, …, c′, d′ are numerical constants called the state variables of the process. We use the compact notation

z(x, y) = \frac{(a, b, c, d)}{(a′, b′, c′, d′)}\binom{x}{y}.

The arithmetic operations can be recovered with suitable choices for the state variables. Thus:

x + y = \frac{(0, 1, 1, 0)}{(0, 0, 0, 1)}\binom{x}{y}
x − y = \frac{(0, 1, −1, 0)}{(0, 0, 0, 1)}\binom{x}{y}
xy = \frac{(1, 0, 0, 0)}{(0, 0, 0, 1)}\binom{x}{y}
x/y = \frac{(0, 1, 0, 0)}{(0, 0, 1, 0)}\binom{x}{y}
\frac{ax + b}{cx + d} = \frac{(0, a, 0, b)}{(0, c, 0, d)}\binom{x}{y}

The last operation is a Möbious transformation in the variable x, since it does not depend on y. It comes from the general expression z(x, y) by replacing y with 0, and may arise from the termination of the stream for y.

Ingesting terms. It is easy to give transformations of the state variables when we ingest one term from x: there are two cases, depending on whether we ingest a partial numerator or a partial denominator. To avoid this dichotomy, it is simplest to ingest a pair of terms at a time. Say the 0th partial denominator q = q_{0} and the 1st partial numerator p = p_{1} of the current x. So

x = q + \frac{p}{x′}

where x′ is the 1st tail of x. Let us see how the state variables changes:

z(x, y) = \frac{a(q + p/x′)y + b(q + p/x′) + cy + d}{a′(q + p/x′)y + b′(q + p/x′) + c′y + d′}
= \frac{(aq + c, bq + d, ap, bp)}{(a′q + c′, b′q + d′, a′p, b′p)}\binom{x′}{y}.

This changes z from a function of x, y to another function of x′, y. In general, if x is a real number and x_{i} is its ith tail, then from (30),

[ \begin{matrix}x \\ 1 \end{matrix} ] = [ \begin{matrix}A_{i} & B_{i} \\ C_{i} & D_{i} \end{matrix} ] [ \begin{matrix}x_{i} \\ 1 \end{matrix} ]
= \frac{(0, A_{i}, 0, B_{i})}{(0, C_{i}, 0, D_{i})}\binom{x_{i}}{y}.

Alternatively, if x is in “complementary form” x = K_{i≥1}(p_{i}/q_{i}) (i.e., q_{0} = 0) then we could write

x = \frac{p_{1}}{q_{1} + x′}

where x′ is now the 1st complement. If we ingest the pair (p, q) = (p_{1}, q_{1}) the transformed function becomes

z(x, y) = \frac{ayp/(q + x′) + bp/(q + x′) + cy + d}{a′yp/(q + x′) + b′p/(q + x′) + c′y + d′}
= \frac{(c, d, ap + cq, bp + dq)}{(c′, d′, a′p + c′q, b′p + d′q)}\binom{x′}{y}.

Egesting terms. Next suppose that we are ready to egest a term from z(x, y). For now, we defer the question of deciding when it is appropriate to egest terms and what these terms should be. Again, it is convenient to assume that we will egest a pair of terms u, v and transform z to z′:

z = u + \frac{v}{z′} .

Then

z′ = \frac{v}{z − u}
= \frac{v}{\frac{axy+bx+cy+d}{a′xy+b′x+c′y+d′} − u}

= \frac{(a′v, b′v, c′v, d′v)}{(a − ua′, b − ub′, c − uc′, d − ud′)}\binom{x}{y}

Similarly, if z is already in the “complementary form”, we can write z = (v/z′) − u, and derive z′ accordingly.

The strategy for deciding when and what terms to egest is simplified by assuming that z is a regular continued fraction (in particular, x, y are real and v = 1 above). The state variables of the process for z contains information about the range of possible values for z. If this range of values are narrowed sufficiently so that we know the value of ⌊z⌋, then we may egest the pair (u, v) = (⌊z⌋, 1) and transform z to z′ as above. It is intuitively clear that without any restriction on the real numbers represented by x, y, there cannot be any á priori bound on how many terms must be ingested before the range is “sufficiently narrow” [16]. But for nice numbers (say algebraic numbers), such bounds exist. In many situations, the range of possible values are can be restricted to intervals of ℝ̂.

Gosper suggests a method of egesting intermediate information without waiting for ⌊z⌋ to be determined. Suppose we have narrowed the range of z so that we know that z lies in [3000, 4000). Then we could egest 3000 and transform z to z′ = z − 3000. Now we know that z′ lies in [0, 1000). If subsequent narrowing of the intervals for x, y tells us that z′ lies in [700, 800), we then egest the two terms 0 and 700, and transform z′ to z′′ = z − 700. Now we know z′′ lies in [0, 100). Suppose we further discover z′′ lies in [20, 30). We then egest the two terms 0 and 20, transforming z′′ to z′′′ = z′′ − 20. Now z′′′ ∈ [0, 10). Say we discover z′′′ ∈ [5, 6). We may then output 0 and 5 and transform z′′′ to z′′′′ = 1/(z′′′ − 5) and continue in the normal fashion. Notice that we have egested the sequence

…, 3000, 0, 700, 0, 20, 0, 5, …

which, by rule (21), is equivalent to egesting one term 3725. The intermediate terms 3000, 700, 20 may be useful, for instance, in narrowing the interval containing z, without waiting for the eventual discovery of the term 3725 (which may not even be necessary). Of course, by having partial denominators that vanish, we have slightly violated the condition for a regular continued fraction. Our example is intended to suggest^{8} the output of decimal representation for partial denominators, but clearly the rule (21) can be applied in more general situations. We can also modify the egestion algorithm to output the value of a continued fraction in human-friendly decimal notation (Exercise).

Intervals. As suggested above, we would like to restrict the range of possible values of z(x, y) to an interval. Suppose x has already egested (i + 1) pairs of terms:

q_{0}, p_{1}, q_{1}, p_{2}, …, q_{i}, p_{i+1}.

Inductively, we may assume that the numerators and denominators P_{i−1}, P_{i}, Q_{i−1}, Q_{i} have been maintained. Therefore x lies in the finite interval with endpoints

P_{i−1}/Q_{i−1}, P_{i}/Q_{i}.

(Recall that i is even iff P_{i−1}/Q_{i−1} < P_{i}/Q_{i}.) Similarly, we may assume that we know the value of y within some interval. We can then deduce an interval containing z. In general, if z(x_{1}, …, x_{n}) is a function where x_{i} are continued functions in complementary form, then the possible values of z is the set z([1, ∞], …, [1, ∞]). If z is one of the arithmetic operations, this set is an interval. We now give an account of intervals and their basic calculus.

An interval I will refer to a connected subset of the extended real numbers ℝ̂. The special case where I = ℝ̂ will be given the special notation ⊥ (this will turn out to be an extension of the use of the symbol ⊥ in §2). If I ≠ ⊥, we will call I a proper interval. We classify proper intervals as follows: I is infinite if ∞ ∈ I, otherwise it is finite. I is positive if it comprises only positive numbers (0 and ∞ are neither positive nor negative). Similiarly for a negative interval. The reader should visualize I using the stereographic projection of I onto the unit complex circle S^{1} (§2, figure 1).

8A more user-friendly output might be ‘3 ∗ ∗∗’, subsequently revised to ‘32 ∗ ∗’, then to ‘327∗’ and finally ‘3275’.

A proper interval I have two endpoints, a and b which are not necessarily distinct. We now introduce some conventions for representing I in terms of a, b. First assume a = b. Then there are two possibilities: either I consists of just the number a or I is equal to ℝ̂ \ {a}. In the former case, I is a point interval denoted I = [a, a]; in the latter case, it is a deleted point interval denoted I = (a, a). We sometimes write a for [a, a]. Next assume the endpoints are distinct and not equal to ∞, say a < b. Suppose I is a closed interval (i.e., a, b ∈ I). Then we can use the notation

I = \{ \begin{matrix}[a, b] & if I is finite \\ [b, a] & if I is infinite \end{matrix}  (53)

If one end point, say b, equals ∞ then we let I = [a, ∞] denote the set of reals that are greater than a including ∞; and I = [∞, a] denotes the set of reals less than a including ∞. If I is open (meaning that both a, b are not in I) then we either write I = (a, b) or I = (b, a) under the same conditions as in (53). We can generalize these notations to half-open intervals (a, b] or [a, b) when a ≠ b, in the standard way. Note that (a, a] and [a, a) are not defined.

Interval calculus. We define algebraic operations on intervals in a generic fashion: assume that f(x, y) and g(x) are algebraic operations on ℝ̂. We extend these operations to any subsets I, J ⊆ ℝ̂ via

f(I, J) :={f(x, y) : x ∈ I, y ∈ J}, g(I) :={g(x) : x ∈ I}.

Now we assume that these operations are continuous and I, J are intervals. Then the result of these operations are intervals. There is an exception to be handled in this generic definition of operations on intervals: it is possible (as usual) that f(x, y) = ⊥ or g(x) = ⊥. By definition, if f(x_{0}, y_{0}) = ⊥ for some x_{0} ∈ I, y_{0} ∈ J then we define f(I, J) = ⊥. But it is also quite possible that f(I, J) = ⊥ even when I × J does not contain such a pair (x_{0}, y_{0}). For instance, [1, −1] + [0, 2] = ⊥ and [2, 1] × [1, 2] = ⊥.

Of course, we are mainly interested in the case where f, g are rational operations. These are wellknown to be continuous. Another useful fact is this: if f(x, y) is monotonic increasing or monotonic decreasing in the finite intervals I, J then the endpoints of f(I, J) (if it is not ⊥) is determined by applying f(x, y) to the endpoints of I and J.

Lemma 6 Let I = [a, b] and I′ = [a′, b′] be proper intervals.

(i) 1/[a, b] = [1/b, 1/a] provided b ≠ ∞. Otherwise, 1/[a, b] = [1/a, 1/b].

(ii) −[a, b] = [−b, −a].

(iii) (Addition) If ∞ ∈ I ∩ I′ then I + I′ = ⊥. If I, I′ are both finite, then I + I′ = [a + a′, b + b′]. Otherwise,

I + I′ = \{ \begin{matrix}⊥ & if a + a′ ≤ b + b′ \\ [a + a′, b + b′] & else \end{matrix}

(iv) (Multiplication) I × I′ = ⊥ iff one of these conditions hold with {I, I′} = {J, J′}: (iv.1) 0 ∈ J, ∞ ∈ J′. (iv.2) J is positive and 0, ∞ ∈ J′ and min(c′ × J) ≤ max(d′ × J) where J′ = [c′, d′]. (iv.3) J is negative and 0, ∞ ∈ J′ and min(d′ × J) ≤ max(c′ × J) where J′ = [c′, d′].

Proof. We only prove (iv). It is clear that I × I′ = ⊥ if condition (iv.1) holds. Assume otherwise. Then (and only then) one of the following cases hold:

(a) ∞ ∉ I ∪ I′.

(b) 0 ∉ I ∪ I′.

(c) {0, ∞} ∩ I = ∅.

(d) {0, ∞} ∩ I′ = ∅. Suppose case (a) holds. Then clearly I × I′ = [min(E), max(E)] where

E = {a, b} × {a′, b′}.

Suppose case (b) holds. Then 1/I and 1/I′ are finite, and the analysis can be reduced to case(a) and part(i) as follows: so 1/(I × I′) = [min(1/E), max(1/E)]. Hence

I × I′ = [1/ max(1/E), 1/ min(1/E)]

(unless max(1/E) = ∞ in which case we exchange the roles of max and min). Cases (c) and (d) are the same except we interchange the roles of I and I′. Assume case (c) holds but cases (a) and (b) do not. This means I is either positive or negative, and {0, ∞} ∈ I′. Then it is easily verified that

I × I′ = \{ \begin{matrix}[min(a′ × I), max(b′ × I)] & if I is positive and min(a′ × I) > max(b′ × I), \\ [min(b′ × I), max(a′ × I)] & if I is negative and min(b′ × I) > max(a′ × I), \\ ⊥ & else. \end{matrix}

This justifies the conditions (iv.2) and (iv.3). Q.E.D.

Using these rules, we can implement arithmetic for continued fractions in which we maintain the intervals as terms are egested and ingested.

Exercises

Exercise 9.1: Consider the process for z(x, y) above.

(i) Carry out the transformations for ingesting a single term of x; likewise, for a single term each from x and from y. (ii) Carry out the transformation for ingesting a pair of terms simultaneously from x and from y. (There are 4 cases depending on whether x, y are in complementary form or not.) (ii) Suppose we only want to ingest one term from either x or y. Discuss heuristics to decide which term should be ingest. □

Exercise 9.2: Modify lemma 6 for open or half-open intervals. □

Exercise 9.3: (Gosper) Let z(x, y) be given by (52). Modify the egestion algorithm above to output the value of z in decimal notation. In particular, we can print the value of any continued fraction in decimal notation. □

Exercise 9.4: Suppose x, y are algebraic numbers of degree at most d and height at most h. Bound (in terms of d, h) the number of terms of x, y that must be egested before we can egest a term of z = x + y. □

Exercise 9.5: (Vuillemin)

An alternative to regular continued fractions we choose the partial denominators q_{i} as follows: Let ⌊r⌉ (rounding of r) denote the integer nearest to a real number r, breaking ties in some systematic way^{9}. For definiteness, we choose ⌊r⌉ = ⌊r⌋ in case of a tie. Then define ZCF(r) = 1/(r − ⌊r⌉). The ℤ-continued fraction of r is the sequence

[q_{0}, q_{1}, …]

where q_{i} = ⌊r_{i}⌉ and r_{0}, r_{1}, … is the sequence r_{0} = r and r_{i+1} = ZCF(r_{i}).

(i) Show that |q_{i}| ≥ 2 for i ≥ 0. (ii) If |q_{i}| = 2 then q_{i+1} has the same sign as q_{i}. (iii) If the sequence [q_{0}, q_{1}, …] terminates then the last term is different from −2. (iv) Replace the rounding function ⌊r⌉ in the definition of the ℤ-continued fraction by a more pragmatic version that can return any value q such that Δ(r, q) < 1 (the chordal metric of §2). Prove that this new continued fraction [q_{0}, q_{1}, …] (which is no longer uniquely determined by r) has the value r. Vuillemin calls this the E-continued fraction of r. □

References

[1] Alan F. Beardon. The Geometry of Discrete Groups. Springer-Verlag, New York, 1983.

[2] M Beeler, R.W. Gosper, and R. Schroepppel. HAKMEM. A.I. Memo 239, M.I.T., February 1972.

[3] D.G. Cantor, P.H. Galyean, and H.G. Zimmer. A continued fraction algorithm for real algebraic numbers. Math. of Computation, 26(119):785–791, 1972.

[4] J. W. S. Cassels. An introduction to Diophantine approximation. Cambridge University Press, 1957.

[5] E. Frank. Continued fractions, lectures by Dr. E. Frank. Technical report, Numerical Analysis Research, University of California, Los Angeles, August 23, 1957.

[6] W.B. Jones and W.J. Thron. Continued fraction: analytic theory and applications. vol. 11, Encyclopedia of Mathematics and its applications. Addison-Wesley, 1981.

[7] Alexey Nikolaevitch Khovanskii. The application of continued fractions and their generalizations to problems in approximation theory. P. Noordhoff N.V., Groningen, the Netherlands, 1963.

[8] D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, 2nd edition edition, 1981.

[9] Lisa Lorentzen and Haakon Waadeland. Continued Fractions with applications. Studies in Computational Mathematics 3. North-Holland, 1992.

[10] Oskar Perron. Die Lehre von den Kettenbrüchen. Teubner, Leipzig, 2nd edition edition, 1929.

[11] Oskar Perron. Die Lehre von den Kettenbrüchen, volume 1. Teubner, Stuttgart, 1954.

[12] Oskar Perron. Die Lehre von den Kettenbrüchen, volume 2. Teubner, Stuttgart, 1957.

[13] A. Pringsheim. Irrationalzahlen und konvergenz unendlicher prozesse. In Encyklopädie der Mathematischen Wissenschaften, Vol.I, pages 47–146, 1899.

[14] Klaus Thull. Approximation by continued fraction of a polynomial real root. Proc. EUROSAM ’84, pages 367–377, 1984. Lecture Notes in Computer Science, No. 174.

9There are four common ways of doing this — always pick the larger, always the smaller, always the smaller magnitude or always the larger magnitude. Thus ⌊1.5⌉ = 2, 1, 1, 2 depending on which of these four rules are used.

Likewise, ⌊−1.5⌉ = −1, −2, −1, −2.

[15] J. V. Uspensky. Theory of Equations. McGraw-Hill Book Co., New York, 1948.

[16] Jean Vuillemin. Exact real computer arithmetic with continued fractions. IEEE Transaction on Computers, 39(5):605–614, 1990. Also, 1988 ACM Conf. on LISP & Functional Programming, Salt Lake City.

[17] H. S. Wall. Analytic theory of continued fractions. Chelsea Publishing Company, Bronx, New York, 1973.