A (i think) related trick: https://kukuruku.co/hub/algorithms/using-the-quick-raise-of-... https://news.ycombinator.com/item?id=8799088
Very cool. Thanks for sharing.
A linear algebra trick for computing Fibonacci numbers fast
41–50 of 76 posts
Re: A linear algebra trick for computing Fibonacci numbers fast
#42Earlier quoted context omitted.
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
Yes, I believe so, up to some multiplicative factor. You can carry out the exponentiations in the field Q[sqrt(5)], which is two-dimentional over Q. The interesting thing here is that diagonalization is trading one 2d vector space for another -- one with a very well-behaved multiplication operation (it's distributive, commutative, associative, and invertible). There's no need to do this to quickly compute fibonacci n…
[dead]
Re: A linear algebra trick for computing Fibonacci numbers fast
#43Earlier 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…
I agree. In fact finding an explanation of pretty much any significant mathematical concept that strikes that balance (across the broad range of individual talents and backgrounds) is time-consuming or difficult.
Which is why a significant chunk of mathematics research effort and funding should go to making such explanations less time-consuming and difficult. IMHO. It may be as simple as a vetted compilation of explanations for a single idea so the individual can find the ones that work for them, or formal development of new explanations. What’s more significant: a new incremental result in some obscure corner of math, or 100M more people understanding what an eigenvalue actually means? Or a new explanation that makes a concept more relevant in an entire application area?
Re: A linear algebra trick for computing Fibonacci numbers fast
#44Hm, no mention of Binet or Bernoulli?
Re: A linear algebra trick for computing Fibonacci numbers fast
#45Well, I am also in the reading group, and I was very happy to see this pop up here. But, all these method, in practicality, leads to integer overflows. Works very well for smaller Fibonacci numbers, but not for, say, the 1500th Fibonacci number. That is very easy and practical to do instead with the naive formula using an array based approach. fibs = [0, 1] for i in range(2,n): fibs.append(fibs[-2] + fibs[-1]) That's…
Python has arbitrary precision integers, so you could do it without running into overflows. Although if implementing floating point based technique, you may want to use np.float128 to handle values upto 10^4932.
> you may want to use np.float128 to handle values upto 10^4932.
I'm not sure the maximum value matters, since I think it only actually gives you 33 decimal digits precision and the 1500th number has over 300 digits.
Although it looks like you'd need to be more careful with it too:
https://numpy.org/doc/stable/user/basics.types.html
> np.float96 and np.float128 are provided for users who want specific padding. In spite of the names, np.float96 and np.float128 provide only as much precision as np.longdouble, that is, 80 bits on most x86 machines and 64 bits in standard Windows builds.
Re: A linear algebra trick for computing Fibonacci numbers fast
#46I 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…
The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.
Re: A linear algebra trick for computing Fibonacci numbers fast
#47I 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
> what if you use the closed-form answer, but without any floating-point or other approximations
You can use a field extension here, ℚ(√5), to represent your numbers. The numbers would be represented as pairs, (a,b), which represents the number a+b√5. You can see for yourself that this set is closed under addition and multiplication.
But when you try to implement code that computes exponents with this representation, you’re probably going to fall back to the old “repeated squaring” trick. But that’s how you calculate exponents with your matrix representation anyway—and you can note that the matrix powers (for this matrix) always take the form
| a b |
| 0 a |
Sometimes these different ideas for representing the problem give us new insight or new algorithms, and sometimes it turns out to be a new perspective on the same piece of code.
Re: A linear algebra trick for computing Fibonacci numbers fast
#48The comparison with the closed form is weird to me: since it uses sqrt(5), I suppose the author intended to use floating point numbers to compute it. But when doing so: - You get a constant time algorithm, since the power function is constant time on most mathematical librarie. Without entering into details on how the pow function is actually computed, on real number you can compute it with: pow(x,y) = exp(y * log(x)…
You can also use exact arithmetic. This is not as bad as it seems, all values you'll encounter are of the form a + sqrt(5) b, with a and b rational (and not even all rationals, but I can't be bothered).
You can even make this somewhat more concrete by using the matrix representation* of a + sqrt(5) b:
[[a, 5b],
[b, a]]
*: The matrix representation is what you get if you view each value a + sqrt(5)b as a vector, and notice that multiplication by a constant is a linear map. The matrices are these linear maps, and it can be shown that matrix addition and multiplication preserve the ring structure. You can forget about the vectors at this point.
Re: A linear algebra trick for computing Fibonacci numbers fast
#49The 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 mean if you want to have the value as a float I reckon the closed form will suit you just fine.
You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again.
It can be quite fast though. I especially like Julia for this. 1) because you can just tell it to use arbitrary precision ints and 2) because you can write a power function that works for everything, floats, ints, matrices with arbitrary precision integers. Which gives one of my favourite one-liners:
fib(n) = ((BigInt [1 1; 1 0])^n)[2,1]
Re: A linear algebra trick for computing Fibonacci numbers fast
#50> 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…
To clarify, you mean treat sqrt(5) as a symbolic constant, and then expand out repeated multiplications of "a + sqrt(5)*b" to arrive at an expression with addition and multplications involving powers of a, b, and sqrt(5)?