{"id":98,"date":"2006-08-03T12:00:09","date_gmt":"2006-08-03T12:00:09","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/08\/03\/something-nifty-a-taste-of-simple-continued-fractions\/"},"modified":"2006-08-03T12:00:09","modified_gmt":"2006-08-03T12:00:09","slug":"something-nifty-a-taste-of-simple-continued-fractions","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/08\/03\/something-nifty-a-taste-of-simple-continued-fractions\/","title":{"rendered":"Something Nifty: A Taste of Simple Continued Fractions"},"content":{"rendered":"

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.
\nYou 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!)
\nIt’s annoying because both fractions and decimals can both only describe
\n*rational* numbers – that is, numbers that are a perfect ratio of two integers. And *most* numbers aren’t rational.
\nBut 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?)
\nSo what do we do?
\nOne 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.
\nLet’s look at an example: 2.3456
\n1. It’s close to 2. So we start with 2 + (0.3456)
\n2. 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 .3088.
\n3. We take the reciprocal again, and get 3, and it’s off by .736
\n4. We take the reciprocal again, and get 1, and it’s off by 0.264
\n5. Next we get 3, but it’s off by 208\/1000
\n6. Then 4, off by 0.168
\n7. Then 5, off by .16
\n8. Then 6, off by .25
\n9. Then 4, off by 0; so now we have an exact result.
\nSo as a continued fraction, 2.3456 looks like:
\n\"continued.jpg\"
\nAs 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].
\nThere’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 much… But let’s look at something simpler: let’s try to write 9\/16ths as a continued fraction. Basically, we make a grid consisting of 16 squares across by 9 squares up and down. 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. Now there’s a rectangle left over: we draw the largest squares we can, there. And so on:<\/p>\n

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

So the continued fraction for 9\/16ths is [0; 1, 1, 3, 2].
\nUsing continued fractions, we can represent *any* rational number in a finite-length continued fraction.
\nOne 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.
\nIrrational numbers are represented as *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.
\nFor 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. Not bad, eh?
\nA very cool property of the continued fractions is: square roots written as continued fractions *always repeat*. Even cooler? What’s the square root of two as a continued fraction? [1; 2, 2, 2, 2, …. ].<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/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":[24,43],"tags":[],"class_list":["post-98","post","type-post","status-publish","format-standard","hentry","category-goodmath","category-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-1A","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/98","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=98"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/98\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=98"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=98"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=98"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}