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