4 ms·
That looks exponentially faster for large n, but with the Fibonacci numbers themselves growing exponentially, the former takes Theta(n^2), while the latter also
by tromp 4y ago
That looks exponentially faster for large n, but with the Fibonacci numbers themselves growing exponentially, the former takes Theta(n^2), while the latter also takes Theta(n^2) for the final squaring of the matrix using naive multiplication and still takes Theta(n^1.58) for multiplication with Karatsuba's algorithm (or still less with the more esoteric methods in [1]).
[1] https://en.wikipedia.org/wiki/Multiplication_algorithm https://en.wikipedia.org/wiki/Multiplication_algorithm
- downvotetruth 4y agohttps://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form Faster Haskell implementations exist as shown on the Haskell page link, but the idea was to show the most straightforward form that is also recursive with an order of magnitude better runtime.