Infinite and Periodic Continued Fractions

Posted on August 1, 2016 by Erik Davis
Tags: number-theory, continued-fractions, haskell

Previously, we worked out some of the basic notions of continued fractions in the special context of rational numbers and their finite expansions. However, much of the charm of the subject arises when one considers the more general case of irrational numbers and infinite continued fractions.

For example, consider the identity \[ \frac{1 + \sqrt{5}}{2} = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}. \] What exactly do we mean by this? Consider, the related problem of making sense of decimal expansions. When we write \[\pi = 3.14159\ldots,\] what do we mean? There are really two things here. First, the ellipsis (\(\ldots\)) means that, although we have written only the first few digits of the decimal expansion, there are infinitely more. Sometimes they are implied by a pattern (as in \(\frac{1}{9} = 0.1111\ldots\)), but other times they are not (as in the above example with \(\pi\)). Second, the equals sign means this this: if we form the sequence \(3, 3.1, 3.14, 3.141,\ldots\), then this sequence converges to the limit \(\pi\). In other words, if we wanted to know the value of \(\pi\) up to a certain error tolerance – say, within \(10^{-11}\) – we can do so by going sufficiently far out in the decimal expansion. And once we have gone this far, adding even more digits of the expansion won’t break our error tolerance.

Likewise with infinite continued fractions. When we say that \[ \frac{1+\sqrt{5}}{2} = 1 + \cfrac{1}{1 + \cfrac{1}{1+\ddots}}, \] we mean that if we form the sequence of convergents \[ 1, \quad 1+\cfrac{1}{1}, \quad 1 + \cfrac{1}{1 + \cfrac{1}{1}}, \ldots, \] then this sequence converges to \(\frac{1+\sqrt{5}}{2}\). More generally, recalling our previous notation, we say that the infinite continued fraction \([a_0,a_1,a_2,\ldots]\) converges to a limit \(x\), written as \[ x = [a_0,a_1,a_2,\ldots], \] if the sequence of convergents \(\frac{p_n}{q_n} = [a_0,a_1,\ldots,a_n]\) converges to \(x\) as \(n\) goes to infinity.

With decimal expansions \[0.d_1 d_2 d_3\ldots,\] any choice of digits \(d_1,d_2,d_3,\ldots\) results in a convergent expansion. With infinite continued fractions, we have a similar phenomena if we restrict ourselves to simple continued fractions1. That is, for any integer \(a_0\) and positive integers \(a_1,a_2,\ldots\), the continued fraction \([a_0,a_1,\ldots]\) converges.

Existence and Uniqueness of Continued Fraction Expansions

Aside from the notion of convergence, in some regards infinite continued fractions are easier to work with than their finite counterparts. For example, when we considered the uniqueness of continued fractions, we encountered a minor difficulty: the last partial quotient could be altered in a trivial way while not changing the value of the continued fraction. For infinite continued fractions, there is no last partial quotient! Hence we have the following.

Every irrational number can be expressed in just one way as an infinite simple continued fraction.

Examples of Infinite Continued Fractions

The process for computing the continued fraction expansion of a general real number proceeds analogously to that laid out in the section on computing expansions of rational numbers, with the important difference that there is now an infinite list of partial quotients. We reproduce our implementation of continuedFraction here.

continuedFraction :: (RealFrac a, Integral b) => a -> [b]
continuedFraction q = n : if r == 0 then [] else continuedFraction (1/r)
  where (n,r) = properFraction q

At the moment, let’s consider the problem of computing continued fractions by hand. Generally speaking, when working with infinite expansions, one hopes to discover some sort of pattern.

For example, let \(x = \sqrt{2} = 1.414\ldots\). Writing \(x\) as a sum of its integer part and fractional part, we have \[x = 1 + (\sqrt{2}-1).\] The idea now is that the fractional part may itself be written as \[ \sqrt{2} - 1 = \frac{1}{\frac{1}{\sqrt{2}-1}} = \frac{1}{\sqrt{2}+1}.\] The algebra in that last equality is simple: by multiplying numerator and denominator by \(\sqrt{2}+1\), we have \[\frac{1}{\sqrt{2}-1} = \frac{\sqrt{2}+1}{2-1} = \sqrt{2}+1.\] Thus \[ x = 1 + \frac{1}{\sqrt{2} + 1}, \] and \(a_0 = 1\).

We may now iterate this procedure. Starting with \(\sqrt{2}+1\) this time, we write \[ \sqrt{2}+1 = 2 + \sqrt{2}-1 = 2 + \frac{1}{\sqrt{2}+1}.\] We see that \(a_1 = 2\), and furthermore a pattern emerges: when starting with \(\sqrt{2} + 1\), the next step in the iteration is again \(\sqrt{2}+1\). This pleasant suprise means that we can stop working, since we know \(a_2 = 2, a_3 = 2, \ldots\). The continued fraction is periodic!

Hence \(\sqrt{2} = [1,2,2,2,\ldots]\). These periodic fractions show up enough that we will simply abbreviate this2 as \[ \sqrt{2} = ([1],[2]). \]

As another example, we now consider \(x = \frac{1+\sqrt{5}}{2}\). Since \(\sqrt{5}\) is bigger than two and less than three, the integer part of \(x\) is 1. We write

\begin{align*} \frac{1 + \sqrt{5}}{2} &= 1 + \frac{\sqrt{5}-1}{2} \\ &= 1 + \frac{1}{\frac{2}{\sqrt{5}-1}} \\ &= 1 + \frac{1}{\frac{1 + \sqrt{5}}{2}}, \end{align*}

where that last step uses the same algebra trick as before. Here again, the iteration reaches a fixed point: starting with \(\frac{1+\sqrt{5}}{2}\), the next step also starts with \(\frac{1+\sqrt{5}}{2}\). Hence we see that \(\frac{1+\sqrt{5}}{2}= [1,1,1,\ldots]\) 3, which in our notation we write succinctly as \[\frac{1+\sqrt{5}}{2} = ([],[1]). \]

In the preceding two examples, the continued fraction expansions ended up being periodic. We shall have more to say on this matter below, but for the moment we mention two continued fractions which are most decidedly not periodic.

Consider \(\pi\). Here the continued fraction looks like this: \[ \pi = [3,7,15,1,292,1,1,1,2,\ldots]. \] Note that my use of \(\ldots\) here should not suggest that there is an apparent pattern: quite the contrary, it suggests simply that the expansion keeps going on and on, with mostly small quotients occasionally interrupted by larger ones.

Whereas the continued fraction expansion of \(\pi\) appears to be quite irregular, just the opposite is the case for \(e\). Here we have \[ e = [2,1,2,1,1,4,1,1,6,1,\ldots], \] with (after the initial \(2\)) the quotients appearing in triplets of the form \(1,2k,1\).4

Floating point arithmetic results in an accumulation of errors, breaking this simple pattern as we see below.

λ> continuedFraction (exp 1)
[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,11,3,2,1,3,1,73,
 6,1,1,1,1,1,2,31,1,1,1,2,1,1,2,1,2,15,9,1,3,1,4,2,1,2,1,2,
 5,5659,1,11,1,1,2,1,1,198,15,5,2,1,1,1,1,...

The expansion becoming increasingly irregular as one goes out further.

Lagrange’s Theorem

When computing the continued fraction expansions of \(\sqrt{2}\) and \(\frac{1+\sqrt{5}}{2}\), we noticed that these were eventually periodic: that is, after some initial quotients, the remaining ones repeat cyclically. 5 For what follows, in an eventually periodic expansion like \(([1,2],[3,4])\), by initial part we shall mean the list of numbers \(1,2\), and by periodic part the list \(3,4\).

It’s no accident that \(\sqrt{2}\) and \(\frac{1+\sqrt{5}}{2}\) have eventually periodic expansions. What these numbers have in common is that they are both quadratic irrationals, that is, irrational roots of quadratic equations with integer coefficients. 6

For some more examples, consider \[ \sqrt{3} = [1,1,2,1,2,1,2,\ldots] = ([1],[1,2])\] and \[ \sqrt{5} = [2,4,4,4,\ldots] = ([2],[4]). \]

This behavior is addressed by the following theorem, due to Lagrange.

Suppose \(x\) is a quadratic irrational. Then the continued fraction expansion of \(x\) is eventually periodic.

A full proof of Lagrange’s theorem is beyond the scope of this article, but more or less it hinges on two ideas:

  1. If we compute the continued fraction expansion of \[ \frac{a + b\sqrt{n}}{d}, \] each iteration involves numbers of the form \(\frac{a' + b'\sqrt{n}}{d'}\).
  2. One can (by way of argument) a priori bound the size of the integers \(a',b',d'\), so that only finitely many intermediate terms are possible.

In an infinite continued fraction, with only finitely many intermediate terms, something is bound to repeat.


The converse to the above theorem was known to be true before Lagrange.

Suppose \([a_0,a_1,a_2,\ldots]\) is eventually periodic.

Then the value \(x = [a_0,a_1,a_2,\ldots]\) is an irrational root of a quadratic equation with integer coefficients.

We sketch a proof of this in a subsequent section.

Computing with Quadratics

We now discuss methods for computing with the continued fraction expansions of numbers of the form \[ \frac{a + b \sqrt{n}}{d}, \] where \(a,b,n,d\) are integers, \(d \neq 0\), and \(n\) is not a perfect square. We shall refer to any real number of this form simply as a quadratic. Here we define a class with the basic data to represent a quadratic, along with a few helper methods.

data Quadratic = Q Integer Integer Integer Integer             
  deriving (Show)

-- The canonical form for a Quadratic is with a,b,d reduced, and d
-- positive. Although the arithmetic will assume n is not a perfect
-- square, we don't check this.
makeQ a b n d | d < 0 = makeQ (-a) (-b) n (-d) 
              | otherwise = Q (a `div` g) (b `div` g) n (d `div` g)
  where
    g = gcd a (gcd b d)

-- We're only going to allow arithmetic between two quadratics if
-- we can do so without getting expressions of a more complicated form.
comparable (Q a b n d) (Q a' b' n' d')
  = (n == n') || (n == 0) || (n' == 0)

-- Tacitly assume x and y are in canonical form.
instance Eq Quadratic where
  x == y = comparable x y && (a,b,d) == (a',b',d')
    where
      (Q a  b  _ d)  = x
      (Q a' b' _ d') = y

-- The algebra here is straightforward. Note that we allow
-- for quadratics that are just rational number, i.e. with
-- n = 0. 
instance Num Quadratic where
  x + y | comparable x y
    = makeQ (a*d' + a'*d) (b*d' + b'*d) (max n n') (d*d')
    where (Q a b n d)     = x
          (Q a' b' n' d') = y

  x * y | comparable x y
    = makeQ (a*a' + b*b'*n) (a*b' + b*a') (max n n') (d*d')
    where (Q a b n d)     = x
          (Q a' b' n' d') = y

  negate (Q a b n d) = makeQ (-a) (-b) n d

  fromInteger x = Q x 0 0 1

  -- We won't be using either of these.
  abs = undefined
  signum = undefined

The number \(\frac{a + b\sqrt{n}}{d}\), assuming \(d > 0\) and \(a,b,d\) have no common divisors, is thus represented as Q a b n d. Note that we do not bother reducing expressions involving square roots, i.e. Q 0 1 8 1 and Q 0 2 2 1 are two distinct representations of \(\sqrt{2}\).

Computing Expansions of Quadratics

As mentioned previously, our implementation of continuedFraction :: (RealFrac a, Integral b) => a -> [b] is valid for any real number with infinite precision arithmetic. Thus if we can make Quadratic an instance of RealFrac, we can get a start on computing infinite continued fractions.


instance Fractional Quadratic where
  recip (Q a b n d)
    = makeQ (d*a) (-d*b) n (a*a - b*b*n)

  fromRational x
    = makeQ (numerator x) 0 0 (denominator x)

instance Ord Quadratic where
  x <= y | comparable x y
    = isPositive (y-x)
    where
      isPositive (Q a b n d)
        | a >= 0 && b >= 0 = True
        | a <= 0 && b <= 0 = False
        | a >= 0 && b < 0  = a^2 >= b^2 * n
        | otherwise        = a^2 <= b^2 * n

instance Real Quadratic where
  -- This will not be used.
  toRational = undefined

instance RealFrac Quadratic where
  -- Note: The use of floating point arithmetic, in the form
  -- of sqrt, will be problematic for large n. However, for
  -- our purposes this is not a problem.
  floor (Q a b n d) = (floor (a' + b'*(sqrt n'))) `div` d'
    where a' = fromIntegral a
          b' = fromIntegral b
          n' = fromIntegral n
          d' = fromIntegral d

  properFraction q = (n, q - fromIntegral n)
    where n = floor q

Trying out \(\sqrt{2} = [1,(2)]\) as a test case, we have

λ> continuedFraction $ makeQ 0 1 2 1
[1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...

as desired.

When \(x\) is a rational number (i.e. \(b = 0\)), we know the computation of the continued fraction expansion terminates in a finite number of steps (specifically, when one of the fractional parts is zero). For quadratic irrationals, Lagrange’s theorem, ensures that the resulting expansion is eventually periodic. Thus we should be able to represent the continued fraction of a general Quadratic (rational or irrational) as an initial part together with a periodic part.

To do so, we will implement a sleight modification to continuedFraction, whereby we keep track of all intermediate numbers produced. That way, when the iteration produces a number that we have seen before (as with the \(\sqrt{2}\) example we did by hand), we can terminate the computation, and split the quotients up appropriately.

To do this, we maintain two pieces of state. First, we have a lookup table, which tells us for each intermediate number the particular iteration in which we last saw it. And second, we keep track of how many terms of the expansion are associated with the initial (non-periodic part). We won’t fully know this until the computation terminates, but this also serves to count the number of iterations so far.

import Control.Monad.State
import qualified Data.Map as M

periodicFraction :: (RealFrac a, Integral b) => a -> State (M.Map a Int, Int) [b]
periodicFraction q = do
  (t,i) <- get
  case (M.lookup q t) of
    Just k ->
      do put (t,k)
         return []
    Nothing ->
      do put (M.insert q i t, i+1)
         let (n,r) = properFraction q
         (n:) <$> (if r == 0 then return [] else periodicFraction (1/r))

initialAndPeriodicParts :: Quadratic -> ([Integer],[Integer])
initialAndPeriodicParts q = splitAt k as
  -- k here is the number of terms in the initial part of the expansion
  where (as,(_,k)) = runState (periodicFraction q) (M.empty,0)

Let’s try a few examples. We’ll compute the initial and periodic parts of a few quadratic irrationals that we know, \(\frac{1+\sqrt{5}}{2} = [(1)]\) and \(\sqrt{2} = [1,(2)]\), as well as a new one: \(\sqrt{7} = [2,(1,1,1,4)]\).

λ> initialAndPeriodicParts $ makeQ 1 1 5 2
([],[1])
λ> initialAndPeriodicParts $ makeQ 0 1 2 1
([1],[2])
λ> initialAndPeriodicParts $ makeQ 0 1 7 1
([2],[1,1,1,4])

Recovering Quadratic Irrationals

If we have a periodic fraction it should correspond to some quadratic irrational \(x\). But how do we compute \(x\)? The answer will show up in the proof that if the continued fraction expansion of \(x\) is eventually periodic, then \(x\) is a quadratic irrational.

Suppose that \(x\) has periodic expansion \(([a_0,a_1,\ldots,a_{L-1}],[a_L,a_{L+1},\ldots,a_{L+k-1}])\), with period \(k\).

Let \(\alpha = [a_L,\ldots,a_{L+k-1},a_L\ldots,a_{L+k-1},\ldots]\) denote the value of the periodic part. This implies the identity \[ \alpha = [a_L,a_{L+1},\ldots,a_{L+k-1},\alpha], \] and so, by the fundamental recurrence, we have

\begin{equation} \alpha = \frac{p' \alpha + p''}{q' \alpha + q''}, \label{eq:alpha} \end{equation}

where \(p''/q''\) and \(p'/q'\) are the last two convergents to \([a_L,a_{L+1},\ldots,a_{L+k-1}]\).

After a bit of algebra with \eqref{eq:alpha}, we see that \(\alpha\) satisfies a quadratic equation with integer coefficients:

\begin{equation} q' \alpha^2 + (q'' - p')\alpha - p'' = 0. \label{eq:alphaquadratic} \end{equation}

Finally, since

\begin{align*} x &= ([a_0,a_1,\ldots,a_{L-1}],[a_L,a_{L+1},\ldots,a_{L+k-1}]) \\ &= [a_0,a_1,\ldots,a_{L-1},\alpha] \end{align*}

we may (again using the fundamental recurrence) obtain \(x\) by

\begin{equation} x = \frac{p_{L-1}\alpha + p_{L-2}}{q_{L-1}\alpha + q_{L-2}}, \label{eq:xalpha} \end{equation}

where \(p_n\) denotes the \(n^{\text{th}}\) convergent of \([a_0,a_1,\ldots,a_{L-1}]\).

Solving for \(\alpha\) in terms of \(x\) in \eqref{eq:xalpha}, and then plugging this in to \eqref{eq:alphaquadratic}, gives a quadratic equation for \(x\) with rational coefficients. Multiplying by the denominators gives a quadratic equation for \(x\) with integer coefficients. \[ \tag*{$\blacksquare$} \]

In the above proof, we didn’t bother deriving explicitly the equation that \(x\) solves. Nonetheless, the proof does give a constructive method for computing \(x\). First, use \eqref{eq:alphaquadratic} to compute \(\alpha\). Then, plug \(\alpha\) in to \eqref{eq:xalpha} to obtain \(x\). Both of these steps involve computing convergents of finite continued fractions. In order to do this, we need code to create Quadratic given as a solution to a quadratic equation with integer coefficients.

-- This is simply the quadratic formula.
quadraticRoots :: Integer -> Integer -> Integer -> (Quadratic, Quadratic)
quadraticRoots a b c = (x1,x2)
  where discriminant = b*b - 4*a*c
        d = 2*a
        x1 = Q (-b) 1 discriminant d
        x2 = Q (-b) (-1) discriminant d

With this, we are ready to implement the aforementioned method.

pairwise f (x,y) = (f x, f y)

recoverIrrational :: ([Integer],[Integer]) -> Quadratic
recoverIrrational (initial,periodic) =
  let ((p', q'):(p'',q''):_) = reverse $ convergents periodic
      (alpha,_) = quadraticRoots q' (q''-p') (-p'')
  in case initial of
       [] -> alpha
       _  -> let ((p',q'):(p'', q''):_) = map (pairwise fromIntegral) $ reverse $ convergents initial   
             in (alpha*p' + p'') / (alpha*q' + q'')

This does exactly what we outlined above. We compute the convergents for the periodic part, and then recover \(\alpha\) as the solution to a quadratic equation. The quadratic equation generally has two roots, so we take the largest one (which is positive). If there’s no initial part, we’re done. Otherwise, we have to use the fundamental recurrence again to recover \(x\).

Let’s try it out. First, recall that \(\frac{1+\sqrt{5}}{2} = ([],[1])\).

λ> recoverIrrational ([],[1])
Q 1 1 5 2

Note that our implementation of Quadratic doesn’t bother to reduce \(\sqrt{n}\), even when possible. Thus we occasionally run into situations like the following:

λ> initialAndPeriodicParts $ makeQ 0 1 7 1
([2],[1,1,1,4])
λ> recoverIrrational ([2],[1,1,1,4])
Q 0 1 252 6

Here our result is valid (\(\sqrt{252}/6 = \sqrt{7}\)), but not fully simplified.

References

  1. Hardy and Wright, An Introduction to the Theory of Numbers, 6th ed.
  2. Khinchin, Continued Fractions.

Footnotes

  1. As in the finite case, we say that the infinite continued fraction \([a_0,a_1,a_2,\ldots]\) is simple if the \(a\)’s are all integers, and \(a_1 > 0, a_2 > 0, \ldots\).↩

  2. Note that this notation is not commonly used in the mathematics literature.↩

  3. There are Fibonacci numbers lurking behind this simple expression. Indeed, from the recurrence \(p_n = p_{n-1} + p_{n-2}\) (recalling that \(a_n = 1\)), we see that the sequence of numerators \(p_0 = 1, p_1 = 2, p_2 = 3, p_3 = 5,\ldots\) differ from the Fibonacci numbers only by a shift of their indices! This also holds true for the denominators \(q_0,q_1,\ldots\).↩

  4. If you’re willing to break our convention that \(a_n > 0\) for \(n = 1,2,\ldots\), you can write this even more elegantly: \(e = [1,0,1,1,2,1,\ldots]\).↩

  5. Formally, could define “eventually periodic” to mean that there exists a \(L\) and \(k > 0\) such that \(a_{l + k} = a_l\) for any \(l \geq L\).↩

  6. In some books, such as Hardy and Wright, quadratic irrationals are referred to as quadratic surds.↩