2 ms·

Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.

by tome 5y ago

thaumasiotes 5y ago
Here'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.

Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.

by tome 5y ago

Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.

Here'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.