Sputsoft

We will be considering continued fractions of the form

where the a_k‘s are real numbers called the partial quotients. Continued fractions can be greatly generalized, where both the “numerators” (here all equal to one) and the partial quotients can be more general mathematical objects. Most common, however, are regular continued fractions where a_0 is an integer and a_1, \ldots, a_n are positive integers. For easier notation we introduce

where /\!/ \, /\!/ = 0 for n=0.

Most of the theory in this article is based on Section 4.5.3 from The Art of Computer Programming, Volume 2, by Donald E. Knuth and Section 6.7 from Concrete Mathematics by Graham, Knuth, and Patashnik. See also Continued Fractions by A. M. Rockett and P. Szüsz.

Basic Properties

Some properties suggest themselves immediately from the definition:

The relations (2) and (3) can be combined into the following,

From (3), (4), and (5) we see that any continued fraction can be written without a zero element (the first partial quotient a_0 may be zero, though) and without the last element being equal to one. For instance,

Continuants

We now turn to continuant polynomials or simply continuants. They are defined as

• K_0() = 1,
• K_1(x_1) = x_1,
• K_n(x_1, \ldots, x_n) = K_{n-1}(x_1, \ldots, x_{n-1}) x_n + K_{n-2}(x_1, \ldots, x_{n-2}) for n \geq 2.

The subscripts are included to make clear how many parameters there are. Note how

where F_0, F_1, \ldots are the well-known Fibonacci numbers (F_0=F_1=0 and F_k=F_{k-1}+F_{k-2} for k \geq 2). This is easily seen by setting x_k=1 for all k in the definition.

We also have

which can be shown straightforwardly by induction. We will use this fact later on.

Continuants are connected to continued fractions in several ways, an essential one being

To prove this identity, we need

We can now proceed with proving (8), which we show by induction. First we observe that it is true for n=0 and n=1,

We now get

which was what we wanted.

A useful equality for continuants is

for n \geq 2. For n=2 we have

and the general case is easily shown using induction. Taking the determinant of both sides of (10) leads to

This shows that when u = K_{n+1}(a_0, a_1, \ldots, a_n) and v = K_n(a_1, a_2, \ldots, a_n) then not only is u/v = a_0 + /\!/ a_1, a_2, \ldots, a_n /\!/, but u and v are also relatively prime.

Evaluating Continued Fractions

Let us consider how to evaluate a continued fraction in C++, given access to the partial quotients a_0, a_1, \ldots, a_n through a forward iterator. One way is to use Equation (1) which leads to

template <typename NUM, typename In>
NUM evaluate_continued_fraction_rec(In first, In last)
{
  if (first == last) return (NUM) 0;
  return *first + evaluate_continued_fraction_rec2<NUM>(first+1, last);
}

where /\!/ a_1, a_2, \ldots, a_n /\!/ is evaluated recursively by

template <typename NUM, typename In>
NUM evaluate_continued_fraction_rec2(In first, In last)
{
  if (first == last) return (NUM) 0;
  return 1/(*first + evaluate_continued_fraction_rec2<NUM>(first+1, last));
}

A drawback to this approach is the recursive calls. Another way to evaluate is to use a special case of Equation (2),

So given a bidirectional iterator the evaluation can be done as

template <typename NUM, typename Bi>
NUM evaluate_continued_fraction_rev(Bi first, Bi last)
{
  if (last == first) return (NUM) 0;
  NUM r = 0;
  while (--last != first)
    r = 1/(*last + r);
  return *last + r;
}

Using continuants, we can actually evaluate a continued fraction using a forward iterator and without any recursive calls. The key is to use the relation (8) which leads to the following algorithm.

template <typename NUM, typename In>
void evaluate_continued_fraction(In first, In last, NUM& num, NUM& den)
{
  if (first == last) { num = 0; den = 1; return; }
  NUM x, u = *first, v = 1, s = 1, t = 0;
  while (true) {
    if (++first == last) { num = u; den = v; return; }
    x = *first;
    s += x*u;
    t += x*v;
    if (++first == last) { num = s; den = t; return; }
    x = *first;
    u += x*s;
    v += x*t;
  }
}

Note how the result is seperated into numerator and denominator. Recall from the previous section that the corresponding fraction is guaranteed to be at its lowest terms.

Constructing a Continued Fraction

Let x be a real number. Consider now the following sequences:

for k = 0, 1, \ldots. We then have

If x_k=0 then a_{k+1}, \ldots are undefined and x = a_0 + /\!/ a_1, a_2, \ldots, a_n /\!/ with n=k. If all x_k‘s are non-zero then x = a_0 + /\!/ a_1, a_2, \ldots /\!/, but we will delay the argument of why this infinite continued fraction makes sense until the final section.

It should be clear from the previous section that the value of the a regular continued fraction is a rational number. So let us try to reverse the process when x is a rational number. Given x=u/v with integer u and positive integer v, how can a_0, a_1, \ldots be computed? Setting u_k/v_k = x_k in the construction process from above, we get

for k = 0, 1, \ldots. If this is turned into a C++ algorithm, we get the following. (The main loop has been unrolled to avoid the u \leftrightarrow v swapping and a little tweaking was also necessary when the algorithm starts because C++ integer division u/v is not always equal to \lfloor u/v \rfloor when the result is negative.)

template <typename NUM, typename Out>
void fraction_to_continued_fraction(NUM u, NUM v, Out out)
{
  if (v < 0) { u = -u; v = -v; }
  NUM r = u % v;
  if (r < 0) { u -= v; r += v; }
  *out++ = u/v;
  u = r;
  while (true) {
    if (!u) return;
    *out++ = v/u;
    v %= u;
    if (!v) return;
    *out++ = u/v;
    u %= v;
  }
}

Notice the resemblence to computing the greatest common divisor using Euclid’s algorithm. In fact, the values of u and v are equivalent to those during the gcd_euclid function of that article. Furthermore, Euclid’s algorithm always terminates, so the construction process always terminates when the input number is rational. In fact, a continued fraction is finite if and only if it represents a rational number.

Infinite Continued Fractions

Let us consider the construction of a continued fraction for any real number x. Recall that at any stage of the construction, we have

How close is x to a_0 + /\!/ a_1, a_2, \ldots, a_k /\!/ for some k? We get

using (1), (8), (11), and (12). This relation shows several important things (which also hold for finite continued fractions x = a_0 + /\!/ a_1, a_2, \ldots, a_n /\!/ when k < n):

• a_0 + /\!/ a_1, a_2, \ldots, a_k /\!/ is less than x for even k and greater than x for odd k.
• Using (8) and (9) we see that the function y \mapsto a_0 + /\!/ a_1, a_2, \ldots, a_k+y /\!/ is continuous and strictly increasing (k even) or strictly decreasing (k odd) when y goes from 0 to 1, and since 0 < x_k < 1 we have that x always lies between a_0 + /\!/ a_1, a_2, \ldots, a_k /\!/ and a_0 + /\!/ a_1, a_2, \ldots, a_k+1 /\!/.
• The denominator of the error term grows, at least, exponentially,
  (13)
  \begin{aligned}
  &K_k(a_1, a_2, \ldots, a_k) K_{k+1}(a_1, \ldots, a_k, 1/x_k) \\
  &\qquad \geq K_k(1, \ldots, 1) K_{k+1}(1, \ldots, 1) = F_{k+1} F_{k+2} \geq (\phi+1)^{k+1}/5,
  \end{aligned}

  using (6), (7) and with \phi = (1+\sqrt{5})/2 \sim 1.618.

• Since the error term goes to zero as n \rightarrow \infty, infinite continued fractions make sense as the following limit,
  a_0 + /\!/ a_1, a_2, \ldots /\!/ = a_0 + \lim_{k\rightarrow\infty} /\!/ a_1, a_2, \ldots, a_k /\!/.

The bound for F_{k+1} F_{k+2} in (13) can be derived by using the formula for the kth Fibonacci number, F_k = (\phi^k – (1-\phi)^k)/\sqrt{5},

where we use that \phi^2-\phi-1=0, \phi(1-\phi)=-1, and 1 < \phi < 2.

As an example of an infinite continued fraction it can be shown that

Evaluating the truncated finite continued fractions 2, 2 + /\!/ 1 /\!/, 2 + /\!/ 1,2 /\!/, and so on, we get

where each fraction is a better and better approximation to e (the absolute error for 49171/18089 is around -3 \cdot 10^{-10}).

As mentioned earlier, the continued fraction of some x is finite if and only if x is rational. The continued fraction representation for x is infinite and eventually periodic,

if and only if x is a quadratic irrationality (proved in TAOCP, vol. 2, Exercise 4.5.3–12). A quadratic irrationality is a number of the form (\sqrt{d}-u)/v where d, u, and v are integers, d > 0, v \neq 0, and d is not a perfect square.

Some special cases of this theorem are:

• \sqrt{n^2+1} = n + /\!/ 2n,2n,\ldots /\!/,
• \sqrt{n^2+2} = n + /\!/ n,2n,n,2n,\ldots /\!/,

for positive integers n. To prove the first of these identities let x = n + /\!/ 2n,2n,\ldots /\!/. Then x-n = y where y = 1/(2n + y), implying x-n = 1/(x+n) and finally x^2-n^2=1. The second identity can be proved similarly.

Concluding Remarks

This article on continued fractions was supposed to be fairly short and just contain the most basic properties, but the subject turned out to be vast and very interesting. More articles related to continued fractions will likely follow.