On: A Fairly Fast Fibonacci Function

[jacobolus]

It’s cheating (or at best misleading) to allow arbitrarily expensive operations to be considered “constant time”.

Raising a very-high-precision approximation of an irrational number to a large integer power will get slower and slower as you handle larger numbers.

You might just as well call the matrix version O(1)

[TheRealPomax → jacobolus]

Not sure if you noticed that's literally what they did at the end of the "Eigenvalue Solution" section, but it reads "So there you have it – a O(1) algorithm for any Fibonacci number."

Although they do note that eigen_fib() completely breaks down once the numbers involved are larger than fit in a 64 bit integer.

[jacobolus → TheRealPomax]

The previous commenter was criticizing https://www.nayuki.io/page/fast-fibonacci-algorithms (for not mentioning the supposedly O(1) solution) not http://www.oranlooney.com/post/fibonacci/