Project 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.
Funny 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].
...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
Careful -- 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!
Yes, 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.
Continued 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.
10 comments
[ 20.0 ms ] story [ 1856 ms ] thread[0] http://pastebin.com/Vp1JsVh0
...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
Still fascinating though.
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.
http://en.wikipedia.org/wiki/Wiener%27s_attack