The Fibonacci sequence is defined by the recurrence,
F(0) = 0
F(1) = 1
F(i) = F(i - 2) + F(i - 1) [For all i ≥ 2]
The series that yield from the above recurrence is
0, 1, 1, 2, 3, 5, 8, 13, …
The Fibonacci series appear throughout nature. The sequence in which rabbit multiply, branch patterns in trees, arrangement of a pinecone etc. are some practical examples.
There are various implementations of the Fibonacci series. Lets look at some of them along with their run times.
The above gist contains the recursive implementation of the Fibonacci series. This is by far the worst implementation of the sequence. The running time of the above algorithm is O(2^n) where n is the input to the recurrence F from above definition. This algorithm might suffice when n is small, but when n is large, the time taken by the program grows exponentially.
The above gist is the iterative implementation of the algorithm. The running time of the algorithm is O(n). This is simple and faster than the above algorithm. For most of the time, this algorithm is fast enough to compute the Fibonacci sequence. But if you still want to push the boundary, there are a few techniques available.
Fibonacci sequence is closely related to the golden ratio (ϕ). It is given by the following formula,
And the Fibonacci number of i is given by
Using the above formula we can calculate the Fibonacci sequence of a given number i. The running time of the above method is O(1). But it is advised that this method is not used in non-mathematical software. This is so because there might be overflows in the floating-point computation and you might not end with the right result.
The fastest way then, in normal circumstances, to find out the Fibonacci sequence of a number i is to use a matrix of a special form and square it recursively. It turns out that
The Fibonacci number is present in the upper right corner and in the lower left corner of the result matrix. For example,
The initial matrix is of a constant size (2x2) and when you multiply the matrix against itself, you get another 2x2 matrix. Only four numbers are used here and this makes the algorithm simple. The running time for this algorithm is O(lg n) which is very fast and this is the algorithm that is mostly used to calculate F(i).
If you have read this far, you should follow me on twitter.
Also feel free to follow my projects on github.