Hacker News Reader

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

View on HN

Exactly. 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-functi...

The 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.

The 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.

The article I linked has code examples in four languages, all use bigints, not longs.

How do you implement multiplication without addition?

Reply on news.ycombinator.com