Speaking of the Fibonacci Sequence

Over at Programming Praxis, a recent problem involved the continued fraction

We can write this as the recursion relation

G₀ = 1

G_n+1 = 1 + 1/G_n

The problem is to find G₂₀₀. It's not hard to see that the G_n converge to some number G and therefore that G = 1 + 1/G, and so G is the golden ratio.

More interesting, though, is that G_n = Fib_n+1/Fib_n, where Fib_n is the n^th Fibonacci number starting from 1—that is, the Fibonacci sequence 1, 1, 2, 3, 5, … . Exercise 1.19 of SICP develops a fast method of calculating Fib_n+1 and Fib_n at the same time in O(log n) time (it's very much like the fast exponential routines). This gives us an elegant and fast solution to the problem

(define golden-ratio
(lambda (n)
(let iter ((n n) (p 0) (q 1) (a 1) (b 1))
  (cond ((= n 0) (/ a b))
        ((even? n) (iter (/ n 2) (+ (* p p) (* q q))
                         (+ (* 2 p q) (* q q)) a b))
        (else (iter (- n 1) p q (+ (* b q) (* a q) (* a p))
                    (+ (* b p) (* a q))))))))

I like this problem because it's a chance to use the fast Fibonacci

calculator from SICP, an opportunity that doesn't come up often.