Sign up with Facebook or Sign up manually
Already have an account? Log in here.
Agnishom Chattopadhyay, Satyabrata Dash, Pranjal Jain, and
- Calvin Lin
- Jimin Khim
contributed
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. \]
Contents
- Recursive Algorithm
- Dynamic Programming
- Matrix Exponentiation
- Double Fibonacci Identities
- Generalized Fast Fibonacci Transform
Recursive Algorithm
The most natural way to calculate the \(n^\text{th}\) Fibonacci number is to use the recursive definition itself.
1234567 | |
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).\)
Dynamic Programming
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).\)
12345 | |
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.
Consider the Fibonacci sequence, defined as follows:
Fibonacci(1) = 1Fibonacci(2) = 1Fibonacci(n) = Fibonacci(n - 2) + Fibonacci(n - 1)The first two Fibonacci numbers are 1, 1. The following elements are computed by adding the prior two.
The first 6 Fibonacci numbers are: 1, 1, 2, 3, 5, 8.
Let F be the \(46^\text{th}\) Fibonacci number. What are the last 3 digits of F?
Note that the above problem is going to be very expensive with recursion.
Matrix Exponentiation
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).\)
Double Fibonacci Identities
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} \]
Generalized Fast Fibonacci Transform
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}.\]
Cite as: Fast Fibonacci Transform. Brilliant.org. Retrieved from https://brilliant.org/wiki/fast-fibonacci-transform/
