Calculating Fibonacci Quickly


We're all familiar with the definition of the fibonacci sequence*:
$$ fib (n) = \left\{ \begin{array}{ll} 0 & \mbox{if $x = 0 $}\\ 1 & \mbox{if $x = 1$}\\ fib(n-1) + fib(n-2) & \mbox{if $x > 1$}\end{array} \right.$$ Which is easily translated into a piece of ML code
    fun fib 0 = 0
       |fib 1 = 1
       |fib n = fib (n-1) + fib (n-2);
What's the cost to calculate $fib (n)$? For $n \geq 2 $, the cost is the cost of recursive calls, plus one to sum them together (setting unit cost to be addition). We need to solve the recurrence relation $$ T(n) = T(n-1) + T(n-2) + 1$$
with $T(0) = T(1) = 1$.


We could work $T(n)$, the time taken to compute the nth Fibonacci number exactly, but then we might as well solve for $fib(n)$ - the recurrence relation is very similar. Rest assured, the cost to compute using this method is exponential.

Let's assume an exponential value for the nth value of the Fibonacci sequence
$$ fib(n) = A\omega^n $$
substituting in, $$ A\omega^n = A\omega^{n-1} + A\omega^{n-2} $$ $$ \omega^2 - \omega - 1 = 0 $$ $$ \omega_1 = \frac{-1 + \sqrt{5}}{2}, \omega_2 = \frac{-1 - \sqrt{5}}{2}$$ Since we have two solutions for $\omega$, the most general solution is $$ fib(n) = A\omega_1^n+ B\omega_2^n $$ where $A$ and $B$ are arbitrary constants. To find the values of these constants, use the contraints $fib(0) = 0$ and $fib(1) = 1$ $$ A + B = 0 $$ $$ A\omega_1 + B\omega_2 = 1$$ $$ A\omega_1 + (1-A)\omega_2 = 1$$ $$ A = \frac {1}{\omega_1 - \omega_2}$$ $$ A = \frac {1}{\sqrt{5}} , B = - \frac {1}{\sqrt{5}} $$ So, noting that $\omega_2 = 1-\omega_1$, we have the solution for $fib(n)$: $$fib(n) = \frac{1}{\sqrt{5}} (\omega_1^n - (1-\omega_1)^n)$$ How long does it take to compute using this method? Using a machine that can exponentiate in contant time, constant time! Of course, no such machines exist, most machines can multiply in constant time, thus exponentiate in logarithmic time. On a real machine, however, we cannot represent a non-rational number exactly, so we may introduce floating point errors, and have to round the answer to the nearest integer. This is pretty messy, so a more preferable method is to use dynamic programming. This is an optimisation of the ML implementation above, where we may calculate the same fibonacci value multiple times - e.g.


The idea behind dynamic programming is to calculate each value once only, even if it is required more than once. This can be implemented by initialising an array of length n with values, -1, say, to mean '$fib(n)$ has not been calculated'. When we call $fib(n)$, first check to see if it has been calculated, and if it hasn't, work it out and change the value of the array at index n to be the value calculated. When we call $fib(n)$, we call $fib(n-1)$ and $fib(n-2)$, and since $n-1>n-2$, $fib(n-2)$ has constant cost - it's already been calculated by the call to $fib(n-1)$. So if the cost of calculating $fib(n)$ is $C(n)$, $$C(n) = C(n-1) + k$$ so $C(n) = O(n)$, we can calculate fibonacci in linear time.

Arrays are not in all ML implementations, and lists take linear time to access, so a more natural way to calculate fibonacci in linear time with ML is to use tail recursion:
      fun fib n = let fun  fibcalc 0 x y = x
                          |fibcalc n x y = fibcalc (n-1) y (y+x) 
                      in 
                      	   fibcalc n 0 1                       
                      end;
Here, we work 'bottom up' to construct $fib(1), fib(2), ... , fib(n)$ which uses constant stack space and still takes linear time.

* We could equivalently define the 0th Fibonacci number to be 1, the 1st to be 1, but it makes the algebra a bit harder.