Mathematics · 3 min read
Fibonacci in O(log n): from matrices to fast doubling in Java
Why the naive Fibonacci is exponential, how a 2×2 matrix turns it logarithmic, and a fast-doubling BigInteger implementation that computes F(1 000 000) in a fraction of a second.