3 ms·

doesn't even mention the closed form O(1) solution..

• mehrdadn 8y ago
  https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma
• jacobolus 8y ago
  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 8y ago
    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 8y ago
      The previous commenter was criticizing https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms (for not mentioning the supposedly O(1) solution) not http://www.oranlooney.com/post/fibonacci/ http://www.oranlooney.com/post/fibonacci/
• Sniffnoy 8y ago
  Closed form O(1) solution? Using Binet's formula, if that's what you mean, is not O(1), for a number of reasons. Firstly, exponentiation is not constant-time. Secondly, how are you going to do it to the necessary precision? Are you really going to use some sort of floating-point number for this? Of course, you could use an exact representation, using a pair of integers (or rational numbers, depending on what basis you use)... but that will be essentially the same as the usual matrix solution. Remember, the n'th Fibonacci number has a number of bits linear in n, and you need at least the time to write all those bits out. That can't be done in O(1), no matter how you do the computation!
• yxhuvud 8y ago
  Eh, it basically derives it, though in matrix form.