Hacker News Reader

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/64b9...

[2] https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form

View on HN

Only 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 :)

That'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!

oic. I missed that nuance. Thanks for the clarification.

Again, neat formula, happy to see your comments :)

Reply on news.ycombinator.com