Lately I’ve been playing around with continued fractions - I blame credit @evelynjlamb for pointing me at this post by @johndcook.

I’ve done most of my learnin’ from here and from various Wikipedia pages, and I thought I’d revisit some of it for the benefit of others.

In fact, I’ll start with the same challenge as Dr Lynn did: compute 37 digits of the square root of two. I’m not going to do that, (I’m going to do about five), but you’ll be able to take it on to 37 if you really want to.

What is a continued fraction?

A “simple” continued fraction looks something like this:

$x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \dots}}}$

with specific values for the $a_i$s - and we typically write the whole thing as $[a_0; a_1, a_2, a_3, \dots]$. Any real number can be written as a simple continued fraction ((I believe, in at most two ways.)) For example, the $a_i$s for $e$ turn out to be $a_0=2$, $a_k = \frac{2}{3}(k+1)$ if $k$ is one less than a multiple of 3, and 1 otherwise. That is to say, $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \dots]$, or

$e = 2 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \dots}}}$

… and what good are they?

One of the things they’re good for is generating rational approximations for irrational numbers - there’s a lot to say on the topic, but I won’t say it. Instead, I’ll outline how to use a continued fraction like the one for $e$ above to generate a good approximation.

You need two starting “fractions”: for reasons I don’t fully understand and can’t be bothered to think about, these are $c_{-2} = 0/1$ (a lower bound) and $c_{-1}= 1/0$ (an upper bound). That’s right; we’re treating 1/0 as if it’s a reasonable thing.

Oh, and since we’re being unreasonable, I’m also going to redefine the addition and multiplication operators for these fractions: in this particular domain, $a/b + c/d = (a+c)/(b+d)$ and $k(a/b) = (ka)/(kb)$, just like we’re forever rolling our eyes at Year 8 students for trying. But here, let’s roll with it.

With all of that in place, the generation rule is, $c_k = a_k c_{k-1} + c_{k_2}$. Let’s try it with $e$:

  • $c_0 = 2(1/0) + (0/1) = (2/1)$ - our first estimate is 2.
  • $c_1 = 1(2/1) + (1/0) = (3/1)$ - our second estimate is 3. Getting better!
  • $c_2 = 2(3/1) + (2/1) = (8/3)$ - that’s 2.67 or so.
  • $c_3 = 1(8/3) + (3/1) = (11/4)$, which is 2.75.
  • $c_4 = 1(11/4) + (8/3) = (19/7)$, or 2.71.
  • $c_5 = 4(19/7) + (11/4) = (87/32)$, or 2.7187 - we’re getting pretty close already!
  • $c_6 = 1(87/32) + (19/7) = 106/39$, giving (2.7179)
  • $c_7 = 1(106/39) + (87/32) = 193/71$, or 2.7183.

… and we can keep going like this until we get bored, or reach some specified accuracy.

How do you work out the continued fraction for $e$?

It’s a secret! By which I mean, it’s too complicated to explain right now. If you’re interested, leave a comment and I’ll write a follow-up post some day.

However, I can tell you how to work out the continued fraction for $\sqrt{2}$.

I want to write $\sqrt{2} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \dots}}$, and we know that $\sqrt{2}$ is between 1 and 2 - so we’d better make $a_0=1$.

So $\sqrt{2}-1 = \frac{1}{a_1 + \frac{1}{a_2 + \dots}}$, only we can flip all of that upside-down to say (*) $\frac{1}{\sqrt{2}-1} = a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \dots}}$.

That left-hand side is (after a bit of a conjugate trick) $\sqrt{2} + 1$, which is between 2 and 3, so $a_1 = 2$.

We now have $(\sqrt{2} + 1) = 2 + \frac{1}{a_2 + \frac{1}{a_3 + \dots}}$, or $\sqrt{2} -1 = \frac{1}{a_2 + \frac{1}{a_3 + \dots}}$

But this is just the same as we had in (*) - so all of the other $a_i$s have to be 2!

The continued fraction for $\sqrt{2}$ is $[1; 2,2,2,\dots]$, or $[1; \bar{2}]$.

We could use the same method as we used for $e$ to generate the convergents of $\sqrt{2}$: 1, 3/2, 7/5, 17/12 and so on.

And what about converting to decimals?

The Mathematical Ninja notes your question with interest. However, I can reveal the method here while they’re not looking.

The technique is to compute the convergents as before, but as soon as two consecutive fractions round down to the same value, write that value $v$ down; then if the two fractions are in the form ($p$ / $q$), replace them with ( $10(p - v q)$ / $q$ ) and carry on.

Here’s what I mean:

  • $c_0 = 1(1/0) + (0/1) = 1/1$, which rounds down to 1.
  • $c_1 = 2(1/1) + (1/1) = 3/2$, which also rounds down to 1, so we need to write down 1 and do some replacement:
    • $c’_0 = 0/1$ - this rounds down to 0;
    • $c’_1 = 10/2$ - this comes from taking 2 away from the top of $c_1$ (to get 1) and multiplying by 10. This rounds down to 5.
  • $c_2 = 2(10/2) + (0/1) = 20/5$, which rounds to 4.
  • $c_3 = 2(20/5) + (10/2) = 50/12$, which is also 4.
    • $c’_2 = 0/5$ (to 0)
    • $c’_3 = 20/12$ (to 1)
  • $c_4 = 2(20/12) + (0/5) = 40/29$, which is also 1.
    • $c’’_3 = 80/12$ (to 6)
    • $c’_4 = 110/29$ (to 3)
  • $c_5 = 2(110/29) + (80/12) = 300/70$ (to 4)
  • $c_6 = 2(300/70) + (110/29) = 710/169$, which is also 4 - have you noticed the decimal expansion dropping out yet?
    • $c’_5 = 200/70$ (to 2)
    • $c’_6 = 340/169$ also to 2

… and so on. The decimal expansion appears by magic. Can you prove that it always works?

It’s a bit of work, and I’ve stopped before the numbers get too horrendous - but in principle, you can use this method to read off as many decimal digits as you want to.