5 ms·
What’s So Great about Continued Fractions?
- RodericDay 12y agoProject Euler has a great series of problems showcasing their power, starting on Problem ~50 or so, up to their relationship to Diophantine Equations and integer solutions to optimization problems.
- spain 12y agoFunny I should see this. Just today I finished section 1-3-3 in the Structure and Interpretation of Computer Programs (SICP) which dealt with continued fractions. I threw my answers up on Pastebin if someone wants to take a look, it's exercises 1.37 through 1.39 [0]. [0] http://pastebin.com/Vp1JsVh0 http://pastebin.com/Vp1JsVh0
- UhUhUhUh 12y agoBrings back old memories of Van Vogt's World of Null-A.
- bazzargh 12y agoAnd there's the rabbithole again...I spent much of last week being fascinated by reading around "Exact Real Arithmetic With Continued Fractions" (https://hal.inria.fr/inria-00075792/document https://hal.inria.fr/inria-00075792/document, PDF). More resources on this on the Haskell wiki: https://wiki.haskell.org/Exact_real_arithmetic https://wiki.haskell.org/Exact_real_arithmetic ...which is a bit mindblowing when so much of what we do uses numbers with limited precision. How can irrational numbers be represented in finite space? Using representations like this: http://en.wikipedia.org/wiki/Periodic_continued_fraction http://en.wikipedia.org/wiki/Periodic_continued_fraction
- grumpy-buffalo 12y agoCareful -- because R is uncountable, there is no system for representing arbitrary irrational numbers with finite strings. All irrational numbers with periodic continued fractions are quadratic irrationals, i.e. they can be written as A + B sqrt(C) where A, B, C are all rational. And of course, that formula immediately provides a much more straightforward way to represent such irrational numbers by finite strings!
- bazzargh 12y agoYes, I avoided the word 'arbitrary'. The references make it clear that what they're dealing with is the computable reals - only a countably infinite subset of R. Other representations get used too (like streams of dyadic rationals), and the computable reals contain more than just quadratic roots - eg: pi - but the computable reals are all you get, and this means there's some rough edges - http://en.wikipedia.org/wiki/Specker_sequence http://en.wikipedia.org/wiki/Specker_sequence. Still fascinating though.
- mvr_ 12y agoIf you are interested, I have been playing with some of these ideas here: https://github.com/mvr/cf https://github.com/mvr/cf
- hellbanner 12y agoIf you want to learn about fractions: http://twinbeard.com/frog-fractions http://twinbeard.com/frog-fractions
- CamperBob2 12y agoContinued fractions show up in odd random places, generally when you need to represent a value as precisely as possible with a ratio of two integers that are, themselves, as small as possible. I was writing code to program an RF synthesizer chip the other day and found myself going back to an old Graphics Gems chapter by Ken Shoemake, after discarding three or four newer implementations of rational approximation solvers that I wasn't happy with for various reasons. Ken's application was for intersection testing (presumably for polygon clipping) on machines with limited precision. It's a great introduction to the topic if you can find it.
- user2994cb 12y agoAnother neat application of continued fractions is Wiener's attack on RSA: http://en.wikipedia.org/wiki/Wiener%27s_attack http://en.wikipedia.org/wiki/Wiener%27s_attack