Nth Fibonacci number matrix solution

It’s easy to implement a 2^n recursive solution and also easy to implement an iterative O(n) solution but implementing an O(log n) solution is trickier. The following has a nice summary of various solutions:

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

I just wanted to add some commentary to matrix solution is Method 4 and 5 above. Here are my whiteboard notes/calculations:

So the key thing is to realise that raising the base matrix below to the power of n will give a value for the nth fibonacci number:

One part of the implementation challenge is dealing with matrices and doing multiplication on them. The other part of the challenge is raising the matrices to a power efficiently. A naive power function will result in O(n) but we can optimise that function to O(log n). This is normally done recursively but can be simulated iteratively using binary operators – see section 4 of the following for an implementation:

https://www.techiedelight.com/power-function-implementation-recursive-iterative/

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *