Fast Fibonacci Transform

Fibonacci series is a sequence of numbers where \(F(n)\) is computed by the summation of the previous two terms. In this wiki, we will be exploring various ways to compute Fibonacci numbers.

For those who do not remember what they are,

\[ F(n) = \left\{\begin{matrix} 0 & n=0\\ 1 & n=1\\ F(n-2) + F(n-1) & \text{otherwise}. \end{matrix}\right. \]

The most natural way to calculate the \(n^\text{th}\) Fibonacci number is to use the recursive definition itself.

1
2
3
4
5
6
7

def fib(n):
   if n==0:
      return 0
   elif n==1:
      return 1
   else:
      return fib(n-1)+fib(n-2)

When this algorithm is run, the program goes all the way down the Fibonacci tree to calculate \(F(n-1)\) and then again all the way down to calculate \(F(n-2)\). Clearly, there is a lot of re-computation going on.

Space Complexity
Note that to calculate \(F(n)\), we have to first calculate \(F(n-1)\) and to calculate \(F(n-1)\), we have to calculate \(F(n-2)\) and so on, all the way to \(F(1)\) and \(F(0)\). So, there are essentially \(n\) levels of recursion. The stack space complexity is hence \(O(n)\)

Time Complexity
Let \(T(n)\) be the time required to compute the \(n^\text{th}\) Fibonacci number. Clearly, \[T(n) = T(n-1) + T(n-2) ,\] which is just the Fibonacci recurrence! Hence, calculating the \(n\text{th}\) Fibonacci number takes time of the order \(F(n)\) or simply \(O(\phi^n).\)

Is there a way to avoid recomputing the previous Fibonacci numbers over and over and to not overload the recursion stack as in the recursion algorithm? One way to do this is to use a bottom-up approach, i.e., to compute the Fibonacci numbers all the way from \(F(0)\) and \(F(1)\) to \(F(n-1)\) and \(F(n-2),\) and hence \(F(n).\)

1
2
3
4
5

def fib(n):
    new, old = 1, 0
    for i in xrange(n):
            new, old = old, new + old
    return old

Clearly, we are only storing at most \(2\) numbers at a time. So, we have a constant space complexity.

The time complexity is \(O(n)\), since we need to run the loop through \(n\) times.

Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(n) = Fibonacci(n - 2) + Fibonacci(n - 1)

Note that the above problem is going to be very expensive with recursion.

From this point onwards, we will use the sole properties of matrices to discover the fast computations of Fibonacci numbers.

\[ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix} .\]

This theorem is trivial but nevertheless, we will prove it.

This statement is obviously true for \(n=1\) since

\[ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^1 = \begin{bmatrix} F_2 & F_1\\ F_1 & F_0 \end{bmatrix}. \]

Assume that it also holds for some \(k\), then we have

\[ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^k = \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \end{bmatrix}. \]

Now, multiplying both sides with \( \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}, \) we have

\[ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1} = \begin{bmatrix} F_{k} + F_{k+1} &F_{k+1}\\ F_{k+1} & F_{k} \end{bmatrix}. \]

This implies

\[\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1} = \begin{bmatrix} F_{k+2} &F_{k+1}\\ F_{k+1} & F_{k} \end{bmatrix} ,\]

which follows from the definition.

Hence, the identity holds for any \(n\). \(_\square\)

This algorithm is only as smart as the dynamic programming until it is implemented with exponentiation by squaring. To do this, we need to realize that \[ A^n = \left\{\begin{matrix} A\left(A^2\right)^\frac{n-1}{2} & \text{for odd } n\\ \left(A^2\right)^\frac{n}{2} & \text{for even } n. \end{matrix}\right. \]

Implemented that way, it takes \(O(\lg n)\) time to calculate \(F(n).\)

The following is a direct consequence of the matrix exponentiation algorithm that enables us to do the same thing with some lesser computations.

\[\begin{align} F_{2n} &= F_{n}(2 F_{n+1} - F_{n}) \\ F_{2n + 1} &=F_{n+1}^2 + F_{n}^2. \end{align} \]

We have

\[ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix}. \]

Squaring both sides,

\[\begin{align} \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n} &= \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix} \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix} \\ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{2n} &= \begin{bmatrix} F_{n+1}^2 + F_{n}^2 & F_{n}F_{n+1} + F_{n}F_{n-1}\\ F_{n}F_{n+1} + F_{n}F_{n-1} & F_{n}^2 + F_{n-1}^2 \end{bmatrix} \\ \begin{bmatrix} F_{2n+1} & F_{2n}\\ F_{2n} & F_{2n-1} \end{bmatrix} &= \begin{bmatrix} F_{n+1}^2 + F_{n}^2 & F_{n}F_{n+1} + F_{n}F_{n-1}\\ F_{n}F_{n+1} + F_{n}F_{n-1} & F_{n}^2 + F_{n-1}^2 \end{bmatrix} . \end{align}\]

Hence, we have

\[\begin{align} F_{2n} &= F_{n}F_{n+1} + F_{n}F_{n-1} \\ F_{2n+1} &= F_{n+1}^2 + F_{n}^2. \end{align} \]

The first identity can be simplified a bit:

\[\begin{align} F_{2n} &= F_{n}F_{n+1} + F_{n}F_{n-1} \\ &= F_n ( F_{n+1} + F_{n-1} ) \\ &= F_n ( F_{n+1} + F_{n+1} - F_{n} ) \\ &= F_n (2 F_{n+1} - F_{n} ) \\ \\ \implies F_{2n} &= F_n (2 F_{n+1} - F_{n} ).\ _\square \end{align} \]

This section requires a better explanation. If you have one, please add it and remove this flag.

We could extrapolate the above idea to recurrences of the form \[ f_{n} = x f_{n-1} + y f_{n-2} \] by using the following matrix form:

\[\begin{pmatrix} x & y \\ 1 & 0\end{pmatrix} \begin{pmatrix} f_{n-1}\\ f_{n-2}\end{pmatrix} = \begin{pmatrix} f_{n}\\ f_{n-1}\end{pmatrix}.\]