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:


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:


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

Leave a Reply

Your email address will not be published.