Wednesday, July 22, 2009

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.

No comments:

Post a Comment