Nit: if number n is given in binary representation in the input, then an O(n)-algorithm runs in exponential time as n is an exponential function of log(n). Hence, log(n)^O(1)-time algorithms for the Fibonacci number are reasonable to exist, unless the decision version of the Fibonacci number is NP-hard.
A linear algebra trick for computing Fibonacci numbers fast
61–70 of 76 posts
Re: A linear algebra trick for computing Fibonacci numbers fast
#62Well, 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…
There are "bignum" implementations for every language. Though I never tested the performance impact on closed-form Fibonacci when a defined double precision >64bit is used.
Your code has an accidentally quadratic runtime (instead of linear). Since the array is appended to, the code regularly increases the memory region and has to move all the previous data over.
You could pre-allocate the memory as n is known ahead. Also you don't need all that memory. You only need to store the last two entries.
Re: A linear algebra trick for computing Fibonacci numbers fast
#63I 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…
Yes! This is close the explanation I first encountered in Hubbard & Hubbard. One of the nicest math textbooks and going from zero up to differential forms.
Re: A linear algebra trick for computing Fibonacci numbers fast
#64I 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…
If anyone wants to read this in book form, Linear Algebra Done Right includes it as an exercise at the end of a very short and readable chapter 5.C on eigenspaces and diagonal matricies. The treatment in thirty-three miniatures describes the steps you take but doesn't mention what you are actually doing (finding eigenvalues) or leave you with any intuition for why this was a natural thing to have tried
Yes, that book (thirty three miniatures) has great content, but a hard read. Basically someone like me needs to go back, read other sources, and spend time on paper to get it.
Re: A linear algebra trick for computing Fibonacci numbers fast
#65Earlier quoted context omitted.
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
I did this years ago to demonstrate to my students that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/ Code winds up looking like: def fib_phi(n) ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i end The exponentiation operation uses basic exponentiation by squaring for performan…
Nice! Thank you for sharing.
Re: A linear algebra trick for computing Fibonacci numbers fast
#66Re: A linear algebra trick for computing Fibonacci numbers fast
#67The 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 writ…
> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes,
It’s easy to prove that
fib(n) And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.
Re: A linear algebra trick for computing Fibonacci numbers fast
#68The 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]] Of course this reduces the whole problem to a matrix exponential again, so it's somewhat pointless.…
That's true. Integers of this form a+b*sqrt(5) are called quadratic integers (https://en.wikipedia.org/wiki/Quadratic_integer), and define a ring for which you can define addition and multiplication rules:
(a+b*sqrt(5)) + (c+d*sqrt(5)) = (a+c) + (b+d)*sqrt(5)
(a+b*sqrt(5)) * (c+d*sqrt(5)) = (ac+5bd) + (ad+bc)*sqrt(5)
Note that seeing the operations this way reduce a bit the number of operations compared to the matrix representation you provided: a multiplication using the formula above require 5 integer multiplications instead of 8 with the matrix [[a, 5b], [b, a]].
But this is only a constant factor improvement: the algorithm complexity is still log(n).
And the same result can be achieved by using the special structure of the matrix: for your representation, the matrix are all toeplitz matrices, and multiplying those kind of matrices require less operations than full generic matrix multiplication. For the representation in the original article, If I remember correctly, the matrices are triangular, and again you can multiply them more efficiently using this specificity.
Re: A linear algebra trick for computing Fibonacci numbers fast
#69Earlier quoted context omitted.
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 writ…
> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) (If you need a hint: use induction), so it should be less than 10⁹ bits, or 128 megabytes. And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.
I may have remembered its size as an ASCII string.
Re: A linear algebra trick for computing Fibonacci numbers fast
#70So I implemented this in Python and did not realize that it could so easily handle very large outputs! Very cool Python. I did have to add the lines listed below to be able to print really big results. It was when setting the input to 1000000 that I could really notice the difference between the elementary algorithm and the matrix mulitplication based version. I thought I would try numPy too but yes, it can only go up to around 92 as an input due to the 64 bit integer limit. I also tried a version in CuPy just for fun. It could use up to 64 bits as well (floats). Interesting that regular Python takes a win here.
import sys
sys.set_int_max_str_digits(1000000)