Continued Fractions in Clojure
One of my favorite things to do, with any language that supports even a tiny amount of laziness (for example, Python’s generators are sufficient here) is to play around with generating continued fraction convergents. These turn out to be the “best possible” rational approximations to any given number if what you want is a small denominator. is a good example of an approximation to , for example; and it is also one of its continued fraction convergents.
A number is rational iff its continued fraction expansion is finite. So why bother with lazy evaluation? Since many irrational numbers have simple forms as continued fractions. For example, , the golden ratio, can be approximated starting from an endless sequence of ones. This fascinates me.
On to the code; it’s so simple! Given a sequence of integers , we define where and . Similarly, we let where and . The two sequences differ only in their seed values, so in clojure we could write
for both of them, where stands for or . Now all we have to do is create the stream of quotients of the hs and ks:
So now to get approximations to , we can just
For instance . Not bad! You can see the fibonacci sequence playing out in there. If you plug in the first few terms of the continued fraction expansion for , we see that both the grade school approximation of and the remarkable known to 祖沖之 back in the fifth century are present. I’m going to try to memorize that one; always felt like too much of a hack to me when I was a kid.
Gist is here.