Computing Fibonacci Numbers in Logarithmic Time
In this post, we’re going to implement an algorithm for computing the \(n\)th fibonacci number. We’ll gradually optimize it and eventually end up with an algorithm that takes \(O(\log n)\) steps, which is much better than the \(n\) steps that most implementations take. I’ll assume some familiarity with complexity analysis. If you know big O notation, you’ll be fine.