*scratch*

vijay's weblog

Speeding up Fibonacci

The following definition of the Fibonacci function is found in almost all introductory programming texts that teach recursion:

(define (fib N)
  (if (or (= N 0) (= N 1))
      1
    (+ (fib (- N 1)) (fib (- N 2)))))

It works fine for very small values of N. But the algorithm starts to show its inefficiency as the value of N gets larger. An attempt to profile (fib 40) in Racket produced the following output:

(time (fib 40))


cpu time: 60763 real time: 61093 gc time: 0
165580141

With inputs like 29, 30 or 40, the function has to make millions of recursive calls. Usually authors just ignore this inefficiency. Lawrence C. Paulson might be an exception. In his book, ML for the Working Programmer, he shows how mathematical induction could be used to optimize this function. His algorithm is simple and is based on the following reasoning:

Each Fibonacci number is the sum of the previous two:

0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5,  3 + 5 = 8 ...

It is easy to define a function that takes a pair of numbers and return their sum:

(define (sum pair) (+ (car pair) (cdr pair)))

Let us define a function that returns a pair that contain the last element of the input along with the sum so that recursively calling it will reproduce the above pattern:

(define (nextfib pair) (cons (cdr pair) (sum pair)))

> (nextfib (cons 0 1))
(1 . 1)
> (nextfib (cons 1 1))
(1 . 2)
> (nextfib (cons 1 2))
(2 . 3)
> (nextfib (cons 2 3))
(3 . 5)
> (nextfib (cons 3 5))
(5 . 8)

To compute the Nth element we just recursively call nextfib N times:

(define (fib n)
  (if (= n 0)
      (cons 0 1)
    (nextfib (fib (- n 1)))))

> (time (fib 40))
cpu time: 0 real time: 1 gc time: 0
(102334155 . 165580141)
> (time (fib 400))
cpu time: 0 real time: 0 gc time: 0
(176023680645013966468226945392411250770384383304492191886725992896575345044216019675
 .
284812298108489611757988937681460995615380088782304890986477195645969271404032323901)

The profiling results show that we indeed have a better performing fibonacci procedure! It is also possible to improve the space efficiency of nextfib if we take advantage of tail call optimization:

(define (nextfib n pair)
  (if (= n 0)
    pair
  (nextfib (- n 1) (cons (cdr pair) (sum pair)))))

(define (fib n)
  (nextfib n (cons 0 1)))

> (time (fib 40))
cpu time: 0 real time: 0 gc time: 0
(102334155 . 165580141)
> (time (fib 400))
cpu time: 0 real time: 0 gc time: 0
(176023680645013966468226945392411250770384383304492191886725992896575345044216019675
 .
284812298108489611757988937681460995615380088782304890986477195645969271404032323901)