janmr blog

Continued Fractions and Continuants

We will be considering continued fractions of the form

where the '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 is an integer and are positive integers. For easier notation we introduce

where for .

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. Ya. Khinchin.

Basic Properties

Some properties suggest themselves immediately from the definition:

(1)

(2)

(3)

(4)

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

(5)

From (3), (4), and (5) we see that any continued fraction can be written without a zero element (the first partial quotient 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

  • ,
  • ,
  • for .

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

(6)

where are the well-known Fibonacci numbers ( and for ). This is easily seen by setting for all in the definition.

We also have

(7)

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

(8)

To prove this identity, we need

(9)

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

We now get

which was what we wanted.

A useful equality for continuants is

(10)

for . For we have

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

(11)

This shows that when and then not only is , but and are also relatively prime.

Evaluating Continued Fractions

Let us consider how to evaluate a continued fraction in C++, given access to the partial quotients 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 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),

(12)

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 be a real number. Consider now the following sequences:

for . We then have

If then are undefined and with . If all 's are non-zero then , 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  is a rational number. Given with integer  and positive integer , how can be computed? Setting in the construction process from above, we get

for . If this is turned into a C++ algorithm, we get the following. (The main loop has been unrolled to avoid the swapping and a little tweaking was also necessary when the algorithm starts because C++ integer division u/v is not always equal to 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 . Recall that at any stage of the construction, we have

How close is to for some ? We get

using (1), (8), (11), and (12). This relation shows several important things (which also hold for finite continued fractions when ):

  • is less than for even and greater than for odd .

  • Using (8) and (9) we see that the function is continuous and strictly increasing ( even) or strictly decreasing ( odd) when goes from 0 to 1, and since we have that always lies between and .

  • The denominator of the error term grows, at least, exponentially,

    (13)

using (6), (7) and with .

  • Since the error term goes to zero as , infinite continued fractions make sense as the following limit,

The bound for in (13) can be derived by using the formula for the th Fibonacci number, ,

where we use that , , and .

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

Evaluating the truncated finite continued fractions , , , and so on, we get

where each fraction is a better and better approximation to (the absolute error for is around ).

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

if and only if is a quadratic irrationality (proved in TAOCP, vol. 2, Exercise 4.5.3-12). A quadratic irrationality is a number of the form where , , and are integers, , , and is not a perfect square.

Some special cases of this theorem are:

  • ,
  • ,

for positive integers . To prove the first of these identities let . Then where , implying and finally . 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.