A linear algebra trick for computing Fibonacci numbers fast
codeconfessions.substack.com
A linear algebra trick for computing Fibonacci numbers fast
1–10 of 76 posts
Re: A linear algebra trick for computing Fibonacci numbers fast
#2This is also a nice way to show that the growth of fib numbers is exponentially bounded.
Re: A linear algebra trick for computing Fibonacci numbers fast
#3The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a finite number of initial cases.
Computing the matrix power by squaring means the sizes of the integers are small until the final step, so that final step dominates the run time.
Re: A linear algebra trick for computing Fibonacci numbers fast
#4I 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
M^N = (P Δ P^-1) * … * (P Δ P^-1)
M^N = P Δ^N P^-1
You see the φ values (1±√5)/2 in the matrix Δ.
Diagonalization of a 2x2 matrix is simple to do on paper. The diagonal of Δ contains the eigenvalues of M, which can be found using the quadratic formula. Proving that this is a correct way to diagonalize any diagonalizable matrix is more of a chore, but for this specific 2x2 matrix, you can just show that that you’ve found the values for P and Δ.
This is very elegant mathematically, but I would not use the closed-form solution if I wanted the exact answer, because you’d need a lot of precision, and that’s inconvenient.
Re: A linear algebra trick for computing Fibonacci numbers fast
#5The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a finite number of initial cases. Computing the matrix power by squaring means the sizes of the integers are small until the final step, so that final step dominates the run time.
All of this gets much easier if you notice that the smaller eigenvalue is less than one. So its contribution becomes exponentially smaller at higher F_i. Hence, you can just take the corresponding power of phi, multiply by some constant I forgot, and round to the nearest integer. No need for an exact formula.
Re: A linear algebra trick for computing Fibonacci numbers fast
#6The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a finite number of initial cases. Computing the matrix power by squaring means the sizes of the integers are small until the final step, so that final step dominates the run time.
I think you're right, and the article says "in some rare cases the method may produce incorrect result due to approximation errors".
Re: A linear algebra trick for computing Fibonacci numbers fast
#7> Another interesting thing to note here is the performance of fib_fast and fib_closed_form algorithms. Both of these algorithms essentially compute the nth power of an expression and therefore their complexities in terms of n are same. However, the golden ratio based algorithm is computing the nth power of a scalar value which can be done much faster than computing the nth power of a 2X2 matrix, thus the difference in their actual run-time performance.
Computing powers of the golden ratio should not be done as scalars, since as other posters noted that requires a lot of precision and makes for a messy computation. It's more simply done on two dimensional numbers of the form a + sqr(5)*b with a and b integers, analogous to complex numbers. Then the computational effort can be seen to equal that of the matrix powers.
Re: A linear algebra trick for computing Fibonacci numbers fast
#8The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a finite number of initial cases. Computing the matrix power by squaring means the sizes of the integers are small until the final step, so that final step dominates the run time.
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".
Re: A linear algebra trick for computing Fibonacci numbers fast
#9This is also a nice way to show that the growth of fib numbers is exponentially bounded.
Yes, that's a good point.
Re: A linear algebra trick for computing Fibonacci numbers fast
#10I 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 accessible to people deeply familiar with the concept of basis vectors.