A Linear Algebra Trick for Computing Fibonacci Numbers Fast
(codeconfessions.substack.com)
from abhi9u@lemmy.world to programming@programming.dev on 06 Nov 2023 14:19
https://lemmy.world/post/7876082
from abhi9u@lemmy.world to programming@programming.dev on 06 Nov 2023 14:19
https://lemmy.world/post/7876082
#programming
threaded - newest
According to the article the linear algebra algorithm has a running time of O(log n)
According to the benchmark in the article it’s already way faster at n = 1000. I think you’re overestimating the cost of multiplication relative to just cutting down n logarithmically.
log_2(1000) = roughly a growth factor of 10. 2000 would be 11, and 4000 would be 12. Logs are crazy.
The article is comparing to the dynamic programming algorithm, which requires reading and writing to an array or hash table (the article uses a hash table, which is slower).
The naive algorithm is way faster than the DP algorithm.
It’s not that hard to check yourself. Running the following code on my machine, I get that the linear algebra algorithm is already faster than the naive algorithm at around n = 100 or so. I’ve written a more optimised version of the naive algorithm, which is beaten somewhere between n = 200 and n = 500.
Try running this Python code on your machine and see what you get:
Here’s what it prints on my machine:
Nice.
I have successfully stuck my foot in my own mouth.
Sweet, Sweet, Linear Algebra
<img alt="" src="https://media.tenor.com/iNNUYSTCCjYAAAAC/spongebob-hate.gif">
I’ll just stick with phi, thank you
How could we live without this?