## Speaking of the Fibonacci Sequence

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

We can write this as the recursion relation

G0 = 1

Gn+1 = 1 + 1/Gn

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

More interesting, though, is that Gn = Fibn+1/Fibn, where Fibn is the nth 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 Fibn+1 and Fibn 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.