This is also a nice way to show that the growth of fib numbers is exponentially bounded.
Any solution to a linear recurrence relation is exponentially bounded by the root(s) of the characteristic polynomial.
A linear algebra trick for computing Fibonacci numbers fast
11–20 of 76 posts
Re: A linear algebra trick for computing Fibonacci numbers fast
#12For the initiated, this is SICP[1] Exercise 1.19. That exercise walks you through a proof without explicitly using linear algebra. I remember having a blast solving this back in the day.
[1] https://web.mit.edu/6.001/6.037/sicp.pdf => page 61
Re: A linear algebra trick for computing Fibonacci numbers fast
#13I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is): M = P Δ P^-1 Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is: M^N = (P Δ P^-1) * … * (P Δ P^-1) If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can b…
(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him. The thirty three miniatures book showed a more abstract proof, which would have been ac…
My own personal experience is that, in linear algebra, there are a lot of different ways to prove the same thing. When you search for a proof of something, you may find a proof that is overly basic and verbose, or a proof that is overly advanced and terse.
Finding an explanation of a linear algebra concept that strikes the right balance can be time-consuming or difficult. This is why you see, for example, a hojillion different articles explaining what quaternions are. Everybody is most comfortable at a different place on the complexity spectrum—from “a vector is (x,y,z), here are rules for how that works” to “a vector space is an abelian group V, field F, and a map in Hom(F,End(V))”.
Re: A linear algebra trick for computing Fibonacci numbers fast
#14Earlier quoted context omitted.
I think you're right, and the article says "in some rare cases the method may produce incorrect result due to approximation errors".
If by "rare cases" one means "for all but a small number of cases".
What's "small" in this case? I only have 32GB of RAM, which is only enough for a vanishingly small set of Fibonacci numbers.
Re: A linear algebra trick for computing Fibonacci numbers fast
#15Earlier quoted context omitted.
(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him. The thirty three miniatures book showed a more abstract proof, which would have been ac…
My own personal experience is that, in linear algebra, there are a lot of different ways to prove the same thing. When you search for a proof of something, you may find a proof that is overly basic and verbose, or a proof that is overly advanced and terse. Finding an explanation of a linear algebra concept that strikes the right balance can be time-consuming or difficult. This is why you see, for example, a hojillion…
That's quite true. And so many books to teach it.
I am a software engineer and don't have a major in math beyond studying discrete math in college. So I really have to work hard to understand these proofs. And I certainly value proofs explained in simple terms. :)
Re: A linear algebra trick for computing Fibonacci numbers fast
#16For the initiated, this is SICP[1] Exercise 1.19. That exercise walks you through a proof without explicitly using linear algebra. I remember having a blast solving this back in the day. [1] https://web.mit.edu/6.001/6.037/sicp.pdf => page 61
Interesting, TIL.
Thanks for sharing. :)
Re: A linear algebra trick for computing Fibonacci numbers fast
#17Earlier quoted context omitted.
If by "rare cases" one means "for all but a small number of cases".
What's "small" in this case? I only have 32GB of RAM, which is only enough for a vanishingly small set of Fibonacci numbers.
79. There are only 79 Fibonacci numbers (starting at 0, counting the 1 twice) that are exactly represented by a double-precision float. That's a lot less than 32GB of RAM.
Re: A linear algebra trick for computing Fibonacci numbers fast
#18I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is): M = P Δ P^-1 Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is: M^N = (P Δ P^-1) * … * (P Δ P^-1) If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can b…
what if you use the closed-form answer, but without any floating-point or other approximations
i mean it all comes out to an integer in the end, all the radicals cancel
i see tromp already suggested a form of this
Re: A linear algebra trick for computing Fibonacci numbers fast
#19It's easier to treat these as linear difference equations with constant coefficients and use the ansatz of λ^{n}. This is morally the same thing but without the need for matrix manipulation.
Knuth, Oren and Patashnik's Concrete Mathematics is full of these and is required reading for discrete math.
Re: A linear algebra trick for computing Fibonacci numbers fast
#20I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is): M = P Δ P^-1 Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is: M^N = (P Δ P^-1) * … * (P Δ P^-1) If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can b…
what if you use the closed-form answer, but without any floating-point or other approximations i mean it all comes out to an integer in the end, all the radicals cancel i see tromp already suggested a form of this
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?