What’s So Great about Continued Fractions? | Hacker News Reader

What’s So Great about Continued Fractions?

blogs.scientificamerican.com

50 pointsjonbaer10 comments

And 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, PDF). More resources on this on the Haskell wiki: 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

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.

Still fascinating though.

If you are interested, I have been playing with some of these ideas here: https://github.com/mvr/cf

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.

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.

If you want to learn about fractions: http://twinbeard.com/frog-fractions

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].

[0] http://pastebin.com/Vp1JsVh0

Another neat application of continued fractions is Wiener's attack on RSA:

http://en.wikipedia.org/wiki/Wiener%27s_attack

Brings back old memories of Van Vogt's World of Null-A.

Reply on news.ycombinator.com