Telling Fibs

by Nicolas Wu

Posted on 16 December 2010

Tags: Haskell, C++

Recently I’ve been asked to interview candidates for a programming position using C++. One of the questions I ask is to implement a function that returns the nth Fibonacci number for a given n. This article compares the linear procedural version of the Fibonacci algorithm with a linear functional version.

For candidates who have never heard of, or can’t remember how the Fibonacci sequence goes, I write out the following sequence, and explain that each new number is the sum of the previous two:

n     : 0, 1, 2, 3, 4, 5, 6, ...
fib n : 1, 1, 2, 3, 5, 8, 13, ...

Good candidates are able to write out the following recursive definition (though I have yet to encounter a candidate that says “that’s my program: it’s in Haskell!”):

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

So far, every good candidate has gone for something along the lines of the following procedural code:

int fib (int n) {
  if (n == 0 || n == 1) {
    return 1;
  }
  else {
    return (fib (n - 1) + fib (n - 2));
  }
}

After asking for the complexity of this algorithm, which is almost invariably incorrectly guessed as O(n²), when it is in fact closer to O(2ⁿ), I usually ask whether or not they can derive a linear time version instead.

Linear Procedural

With help, good candidates have been able to come up with something along the following lines:

int fib (int n) {
  if (n == 0 || n == 1) {
    return 1;
  }

  int m    = 2;
  int fib2 = 1;
  int fib1 = 1;
  int fibm = 2;

  while (m < n) {
    m    = m + 1;
    fib2 = fib1;
    fib1 = fibm;
    fibm = fib1 + fib2;
  }
  return fibm;
}

We can prove that this algorithm works by looking at the invariant, and the variant of the loop body. The invariant proves correctness, while the variant proves termination of this code.

The invariant is a condition that must be true before entering and after exiting the loop body. In our case, we establish the following conditions:

fib1 = fib (m - 1)
fib2 = fib (m - 2)
fibm = fib (m - 1) + fib (m - 2) = fib m

It’s easy to check that this is true when we first enter the body of the loop, and while it’s a little tedious, since we’re not making use of multiple assignment (where we can simultaneously change values), we can also show that the invariance holds in the loop body.

The loop variant is used to show that the algorithm is progressing towards its goal. In our case, it is enough to show that the distance from m to n is decreasing. By expressing the old value of m as m₀, we have:

| n - m | < | n - m₀ |

In terms of execution speed, it’s easy to see that this is a linear time algorithm: the main body of the loop is executed n times, and the operations in the body are all constant time.

Linear Functional

In Haskell, a linear time version is remarkably simple to express:

> fibs :: [Int]
> fibs   = 1 : fibs'
> fibs'  = 1 : fibs''
> fibs'' = zipWith (+) fibs fibs'

The nth Fibonacci can be extracted using a simple list lookup:

> fib :: Int -> Int
> fib n = fibs !! n

This is a linear time algorithm because the fibs stream is constructed in linear time: each new element of the list is calculated by adding the previous two values, which is a constant time operation. Looking up values in a list is also done linear time.

Conclusion

It’s interesting to see the procedural and the functional versions of these algorithms side by side, and I think it’s no exaggeration to say that the correctness of the functional ones is much easier to see than the correctness of the procedural ones.

As a means of discerning how good a candidate is, I’ve found that implementing fibs has been a particularly telling measure: bad candidates take a very long time to get to the end of the question, while only very good candidates have been able to derive a linear version of the algorithm.

Comments