{"id":725,"date":"2008-12-30T08:05:21","date_gmt":"2008-12-30T08:05:21","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/12\/30\/continued-fractions-classic-repost\/"},"modified":"2008-12-30T08:05:21","modified_gmt":"2008-12-30T08:05:21","slug":"continued-fractions-classic-repost","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/12\/30\/continued-fractions-classic-repost\/","title":{"rendered":"Continued Fractions (classic repost)"},"content":{"rendered":"

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.<\/em><\/p>\n

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.<\/p>\n

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!)<\/p>\n

It’s annoying because both fractions and decimals can both only describe rational<\/em> numbers – that is, numbers that are a perfect ratio of two integers. The problem with that is that most<\/em> numbers aren’t rational. Our standard notations are incapable<\/em> of representing the precise values of the overwhelming majority of numbers!<\/p>\n

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<\/em> 22\/7?)<\/p>\n

So what do we do?<\/p>\n

<\/p>\n

One of the answers is something called continued fractions<\/em>. 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<\/em>. 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<\/em>. 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<\/em> correction.<\/p>\n

Let’s look at an example: 2.3456.<\/p>\n

    \n
  1. It’s close to 2. So we start with 2 + (0.3456).<\/li>\n
  2. Now, we start approximating the fraction. The way we do that is we take the reciprocal<\/em> 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.<\/li>\n
  3. We take the reciprocal again, and get 3, and it’s off by 0.736.<\/li>\n
  4. We take the reciprocal again, and get 1, and it’s off by 0.264.<\/li>\n
  5. Next we get 3, but it’s off by 208\/1000.<\/li>\n
  6. Then 4, off by 0.168.<\/li>\n
  7. Then 5, off by 0.16.<\/li>\n
  8. Then 6, off by 0.25.<\/li>\n
  9. Then 4, off by 0; so now we have an exact result.<\/li>\n<\/ol>\n

    So as a continued fraction, 2.3456 looks like:<\/p>\n

    \"continued.jpg\"<\/p>\n

    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].<\/p>\n

    \"nine-by-sixteen.png\"<\/p>\n

    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.<\/p>\n

    \"nine-by-sixteen-step1.png\"<\/p>\n

    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:<\/p>\n

    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:<\/p>\n

    \"nine-by-sixteen-step2.png\"<\/p>\n

    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.<\/p>\n

    \"nine-by-sixteen-last.png\"<\/p>\n

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

    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.<\/p>\n

    Using continued fractions, we can represent any<\/em> 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. <\/p>\n

    So, as I just said, we represent irrational numbers using infinite<\/em> 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.<\/p>\n

    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.<\/p>\n

    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, …].<\/p>\n","protected":false},"excerpt":{"rendered":"

    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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13,43],"tags":[],"class_list":["post-725","post","type-post","status-publish","format-standard","hentry","category-classics","category-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bH","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/725","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=725"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/725\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=725"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=725"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=725"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}