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

(defn- step [x-2 x-1 [a & as]]
  (when a
    (let [x (+ (* a x-1) x-2)]
      (cons x (lazy-seq (step x-1 x as))))))

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:

(defn convergents [as]
  (let [c (fn c [[h & hs] [k & ks]]
            (when (and h k)
              (cons (/ h k) (lazy-seq (c hs ks)))))]
    (c (step 0 1 as) (step 1 0 as))))

So now to get approximations to , we can just

(->> 1 repeat convergents (take 20) println)
; (1 2 3/2 5/3 8/5 13/8 21/13 34/21 55/34 89/55 144/89
;  233/144 377/233 610/377 987/610 1597/987 2584/1597
;  4181/2584 6765/4181 10946/6765)

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.

(println (convergents '(3 7 15 1 292 1 1 1)))
; (3 22/7 333/106 355/113 103993/33102 104348/33215 208341/66317 312689/99532)

Gist is here.