Calculating the Fibonacci Numbers

If, like me, you’re fascinated by the Fibonacci numbers you should take a look at Robin Houston’s The Worst Algorithm in the World post over at the Bosker Blog.

Houston lists and analyzes the three main ways of calculating fib(n):

• The naïve recursive method that results from programming right from the definition

  (define fib-rec
    (lambda (n)
      (if (< n 2)
          n
          (+ (fib-rec (1- n)) (fib-rec (- n 2))))))
  

• The iterative method, which can be seen as a dynamic programming solution

  (define fib-it
    (lambda (n)
      (let fib ((k n) (a 1) (b 0))
        (if (zero? k)
            b
            (fib (1- k) (+ a b) a)))))
  

• The logarithmic method, which is similar to fast exponentiation (see Exercise 1.19 of Structure and Interpretation of Computer Programs)

  (define fib-log
    (lambda (n)
      (define sum-of-squares
        (lambda ( a b)
          (+ (* a a) (* b b))))
      (define fib
        (lambda (n p q a b)
          (cond ((= n 0) b)
                ((even? n) (fib (/ n 2) (sum-of-squares p q)
                                 (+ (* 2 p q) (* q q)) a b))
                (else (fib (- n 1) p q (+ (* b q) (* a q) (* a p))
                            (+ (* b p) (* a q)))))))
      (fib n 0 1 1 0)))
  

Readers of this blog will know that the recursive method is horribly inefficient and Houston shows that, in fact, calculating (fib-rec n) takes 2 × fib_n+1 – 1 calls to fib-rec. Thus (fib-rec 100) calls fib-rec 1,146,295,688,027,634,168,201 times.

We’re used to seeing just the first few terms (0, 1, 1, 2, 3, 5, …) of the Fibonacci sequence and it’s easy to forget how rapidly it grows. Here are the values of fib_n for some relatively small n:

Another interesting thing that Houston points out is that the iterative method is actually O(n²) not O(n) as often supposed. That’s because when the numbers get large you must use a multiprecision numeric library and can no longer add the terms in constant time.

Finally, Houston gives a nice way of looking at fib-log and why it works. As I say, this is a really interesting post and worth a few minutes of your time.