4 ms·
Regarding Fibonacci, the recursive formula is much more efficient anyway! Oh, not _that_ recursive formula. That one: [1], from [2]. Basically, it allows you to
by qsantos 3y ago
Regarding Fibonacci, the recursive formula is much more efficient anyway! Oh, not _that_ recursive formula. That one: [1], from [2]. Basically, it allows you to implement in O(log n) arithmetic operations.
[1] https://wikimedia.org/api/rest_v1/media/math/render/svg/64b95fd1ea97b7a4315e8ee4ddb7f6b44c7681f0 https://wikimedia.org/api/rest_v1/media/math/render/svg/64b9...
[2] https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
- hansvm 3y agoOnly under the word-RAM model of computation though. The phrase "arithmetic operation" is doing a lot of heavy lifting. On a real computer, the output size of Fib is O(2^n), requiring O(n) bits of space, and O(n) assembly instructions (at a minimum, and for other reasons that minimum can be attained). The exponential nature of the problem additionally means you hit that Big-O curve for extraordinarily small inputs (as opposed to, e.g., a hash table where technically access isn't O(1) but nobody cares). Separately though, that's a fun trick :)
- qsantos 3y agoThat's why I phrased it that way. But since you mentioned working modulo 2^64, I thought that would count :-). It's useful to make it explicit anyway for people who might miss that, so thanks!
- hansvm 3y agooic. I missed that nuance. Thanks for the clarification. Again, neat formula, happy to see your comments :)