## 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_{0} = 1

G_{n+1} = 1 + 1/G_{n}

The problem is to find G_{200}. 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.

## No comments:

## Post a Comment