3 ms·
> If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods. I don't thin
by thaumasiotes 5y ago
> If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.
I don't think that's true; you're pretty much always better off calculating Fibonacci numbers by starting from F_0 and counting up than by using the closed-form solution.
- tome 5y agoAre you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.
- thaumasiotes 5y agoHere's an article talking about it: https://towardsdatascience.com/why-is-the-closed-form-of-the-fibonacci-sequence-not-used-in-competitive-programming-674b805da341 https://towardsdatascience.com/why-is-the-closed-form-of-the... It covers a couple of points (all of this is me summarizing the article I just linked; I'm not an expert in numeric computing): - The closed-form expression for Fibonacci numbers involves an irrational number. But we can't do computations on irrational numbers; we're stuck with rational approximations. (Such as IEEE floating point.) Since computing an early Fibonacci number involves raising ϕ to a high exponent, the error involved in giving ϕ a finite representation rapidly compounds, corrupting the result. (According to this article, errors will become visible after F_100. That's quickly enough that you'd be justified in just having a lookup table for the first 100 Fibonacci numbers, which would be much faster than computing them as needed.) - You can represent the Fibonacci recurrence relation directly in matrix form. This is just the counting-up method written down a different way. Each Fibonacci number is the product of the constant matrix [[1 1] [1 0]] with the vector consisting of the previous two Fibonacci numbers. - You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.
- tome 5y ago> You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic. Right, and repeated squaring can give you the answer to the exponentiation in logarithmic time.