3 ms·
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1]) https://wiki.haskell.org/The_Fibonacci_sequence https://wiki.haskell.org/The_Fibonacci_sequence
by downvotetruth 4y ago
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])
https://wiki.haskell.org/The_Fibonacci_sequence https://wiki.haskell.org/The_Fibonacci_sequence
- tromp 4y agoThat 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.
- bibanez 4y agoThis isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci