Algorithms – Optimizing nth Fibonacci Number

Let me make it clear beforehand. Don’t misinterpret the heading. I am not going to talk about the Fibonacci optimization technique using memoization and DP where you  store the result of sub-problems to make the algorithm faster. That’s the old school optimization technique which has a time complexity of O(n) and an equivalent space complexity. There is an even better optimization technique which I came across in one of my graduate classes (where I am a student:D).  I will be talking about a new way of representing the Fibonacci series which will help us compute the results way faster than the other techniques.

For those of you who do not know what a Fibonacci series is – It is a number series of the form 1 1 2 3 5 8… etc where the (i)th number in the series is the sum of the (i-1)th and (i-2)th numbers.

We can represent Fibonacci series using matrices as shown below.
[[Fib n][Fib n-1]] = [[1 1][1 0]] * [[Fib n-1][Fib n-2]].

So if we take the dot product, we get the following result
Fib n = Fib n-1 * Fib n-2  and
Fib n-1 = Fib n-1

If we generalize the above matrix multiplication, we get that
[[Fib n][Fib n-1]] = ( [[1 1][1 0]] )^(n-1) * [[Fib 1][Fib 0]].

And we already know that Fib 1 = 1 and Fib 0 = 0. If you look at it, you can see that we have reduced the problem into finding the (n-1)th power of the 2×2 matrix ,[[1 1][1 0]].

Hopefully, you are already aware that it is easy to find the (n)th power of an integer ‘A’ in log(n) operations. This algorithm recursively converts Pow(A,n) to Pow(A*A, n/2) which reduces the size of n by half at each step. The only difference is that, in our particular case, A is a 2×2 matrix instead of an integer.

Thus we have reduced the complexity of finding the (n)th Fibonacci number from O(n) to O(logn) which is a huge improvement when it comes to large values of n.