3 ms·
If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication.
by cousin_it 9y ago
If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication. https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms
- engnr567 9y agoExactly. And fibonacci numbers also have a closed form which can be (in theory) evaluated in O(1): http://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html http://austinrochford.com/posts/2013-11-01-generating-functi...
- cousin_it 9y agoThe number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.
- engnr567 9y agoThe matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.
- cousin_it 9y agoThe article I linked has code examples in four languages, all use bigints, not longs.
- e12e 9y agoHow do you implement multiplication without addition?