Continued Fractions (classic repost)

I'm away on vacation this week, taking my kids to Disney World. Since I'm not likely to
have time to write while I'm away, I'm taking the opportunity to re-run an old classic series
of posts on numbers, which were first posted in the summer of 2006. These posts are mildly
revised.

One of the annoying things about how we write numbers is the fact that we generally write things one of two ways: as fractions, or as decimals.

You might want to ask, "Why is that annoying?" (And in fact, that's what I want you to ask, or else there's no point in my writing the rest of this!)

It's annoying because both fractions and decimals can both only describe
rational numbers - that is, numbers that are a perfect ratio of two integers.
The problem with that is that most numbers aren't rational. Our standard
notations are incapable of representing the precise values of the overwhelming majority of numbers!

But it's even more annoying than that: if you use decimals, then there are lots of
rational numbers that you can't represent exactly (i.e., 1/3); and if you use fractions, then
it's hard to express the idea that the fraction isn't exact. (How do you write π as a
fraction? 22/7 is a standard fractional approximation, but how do you say π, which is almost 22/7?)

So what do we do?

One of the answers is something called continued fractions. A continued fraction is a
very neat thing. Here's the idea: take a number where you don't know it's fractional form.
Pick the nearest simple fraction 1/n that's just a little bit too large. If you were looking at, say, 0.4, you'd take 1/2 - it's a bit bigger. Now - you've got an approximation, but it's too large. So that means that the demoninator is too small. So you add a correction to the denominator to make it a little bit bigger. And you just keep doing that - you approximate the correction to the denominator by adding a fraction to the denominator that's just a little too big, and then you add a correction to that correction.

Let's look at an example: 2.3456.

1. It's close to 2. So we start with 2 + (0.3456).
2. Now, we start approximating the fraction. The way we do that is we take the reciprocal of 0.3456 and take the integer part of it: 1/0.3456 rounded down is 2 . So we make it 2 + 1/2; and we know that the denominator is off by 0.3088.
3. We take the reciprocal again, and get 3, and it's off by 0.736.
4. We take the reciprocal again, and get 1, and it's off by 0.264.
5. Next we get 3, but it's off by 208/1000.
6. Then 4, off by 0.168.
7. Then 5, off by 0.16.
8. Then 6, off by 0.25.
9. Then 4, off by 0; so now we have an exact result.

So as a continued fraction, 2.3456 looks like:

As a shorthand, continued fractions are normally written using a list notation inside of square brackets: the integer part, following by a semicolon, followed by a comma-separated list of the denominators of each of the fractions. So our continued fraction for 2.3456 would be written [2; 2, 3, 1, 3, 4, 5, 6, 4].

There's a very cool visual way of understanding that algorithm. I'm not going to show it for 2.3456, because it's a bit too complicated - it would be hard to draw out the complete diagram for in a legible way. So instead, we'll look at a simpler number to make the visual work. Let's write 9/16ths as a continued fraction. Basically, we make a grid consisting of 16 squares across by 9 squares up and down, like this one.

We draw the largest square we can on that grid. The number of squares of that size that we can draw is the first digit of the continued fraction. For 9/16ths, we can draw one 9×9 square - so our first digit is one, and we're left with a 7×9 rectangle:

Now we just repeat: draw the largest square we can. That's a 7×7, and we can only draw one of it. So the second digit is one; and we're left with a 7×2:

And repeat: the largest square we can draw is a 2×2, and we can draw three of them. So the next digit is a three; and we're left with 1×2 - which is 2 1×1, so the last digit is a 2.

So the continued fraction for 9/16ths is 1/(1+1/(1+3/(1+2))), or [0; 1, 1, 3, 2].

One incredibly nifty thing about this way of writing numbers is: what's the reciprocal of 2.3456, aka [2; 2, 3, 1, 3, 4, 5, 6, 4]? It's [0; 2, 2, 3, 1, 3, 4, 5, 6, 4]. We just add a zero to the front as the integer part, and push everything else one place to the right. If it was a zero in front, then we would have removed the zero and pulled everything else one place to the left.

Using continued fractions, we can represent any rational number in a finite-length continued fraction. We still can't directly represent irrational numbers - they're going to be infinite continued fractions. But we can usually write some expression
to show how to continue the number, and for a given precision, we can approximate
irrational numbers with a much smaller representation.

So, as I just said, we represent irrational numbers using infinite continued fractions. So there's an infinite series of correction fractions. You can understand it as a series of every-improving approximations of the value of the number. And you can define it using a recurrence relation (that is, a recursive formula) for how to get to the next digit -
that recurrence relation is the real key - we can include a simple equation that describes
how, given the current finite continued fraction, to generate the next step.

For example, π = [3; 7, 15, 1, 292, 1, ...]. If we work that out, the first six places of the continued fraction for pi work out in decimal form to 3.14159265392. That's correct to the first 11 places in decimal. So 9 numerals of continued
fractions gives us 11 decimal places. In general, the conciseness savings of continued fractions is even better than that.

I'll close with a very cool property of continued fractions. The square root of most
numbers (excepting the perfect squares) is irrational. In continued fractions,
they're still irrational - that is, they're infinite continued fractions. But all irrational
square roots form repeating continued fractions. The coolest example of this? The square root of 2 in continued fractions is [1; 2, 2, 2, 2, ...].