6 ms·
A linear algebra trick for computing Fibonacci numbers fast
- davesque 3y agoThis is also a nice way to show that the growth of fib numbers is exponentially bounded.
- pfdietz 3y agoThe 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.
- munchler 3y agoI think you're right, and the article says "in some rare cases the method may produce incorrect result due to approximation errors".
- pfdietz 3y agoIf by "rare cases" one means "for all but a small number of cases".
- tedunangst 3y agoWhat's "small" in this case? I only have 32GB of RAM, which is only enough for a vanishingly small set of Fibonacci numbers.
- chowells 3y ago79. 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.
- __rito__ 3y agoYup, I implemented all these, and only naive Python array based approach is the most practical, Python being a GC language. For all other things that I tried, I either get integer overflows (for linear algebra based implementations) or floating point errors (for the closed form).
- scythe 3y agoAll 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.
- contravariant 3y agoI 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] Last time I checked a manual implementation of exponentiation through squaring is just as fast as the native one. If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, beyond that points things get a bit tricky.
- Someone 3y ago> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^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.
- contravariant 3y agoI may have remembered its size as an ASCII string.
- pfdietz 3y ago> 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. The time will be dominated by the time to multiply integers in the final stage of the repeated squaring, which is superlinear in the number of bits. (1) (1) for fixed word size. One might instead argue it's a function of the number of words (# of bits/word size) and that the word size must eventually increase as integers get larger, asymptotically.
- dietrichepp 3y agoI 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 be removed, giving: M^N = P Δ^N P^-1 The powers of a diagonal matrix is done by taking powers of the entries on the diagonal. 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.
- abhi9u 3y ago(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.
- dietrichepp 3y agoMy 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))”.
- tromp 3y ago> 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.
- jonahx 3y agoTo 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)?
- margalabargala 3y agoThis is correct. All fibonacci numbers are integers, thus all instances of sqrt(5) must eventually cancel out.
- deleted 3y ago[deleted]
- reginaldo 3y agoFor 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 https://web.mit.edu/6.001/6.037/sicp.pdf => page 61
- nimish 3y agoIt'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.
- mahalex 3y agoNote that “Oren and Patashnik” is one person named Oren Patashnik.
- nimish 3y agoThanks! The correct authors are Graham, Knuth, and Patashnik.
- giik 3y agoI came here to say the same: difference equations, z-transform, recurrence relations, are (or used to be) standard undergrad eng curriculum (typically via some required Signals & Systems course). Maybe not so popular in the CS world though? Beautiful expo on the subject: https://eee.guc.edu.eg/Courses/Communications/COMM401%20Signal%20&%20System%20Theory/Alan%20V.%20Oppenheim,%20Alan%20S.%20Willsky,%20with%20S.%20Hamid-Signals%20and%20Systems-Prentice%20Hall%20(1996).pdf https://eee.guc.edu.eg/Courses/Communications/COMM401%20Sign... (Chapter 10, etc.)
- SuchAnonMuchWow 3y agoThe 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)). It is not visible on the performance graph probably because the matrix-based algo and the closed formula are dwarfed by the linear time algo. - You gen an incorrect result very quickly: not even considering the fact that sqrt(5) can not be represented exactly by a floating point number, the result will be out of the range of floating point numbers with n proportional to the number of bits your floating point number holds, so probably between n=50 and n=100.
- abhi9u 3y agoAuthor here: At the time of writing, I was not aware that the matrix form and the closed form are same, because you can derive the golden ratio based formula from the matrix formula. Full disclaimer: I am not a math major, and I can make such mistakes :) Although, I am curious to learn about exponentiation of real numbers. While writing this article, I was investigating how different libraries/languages implement exponentiation. While for matrix exponentiation, numpy used the algorithm I showed in the article. I also looked at the pow() function in libm of FreeBSD and it used the form you provided. I've been trying to look at an explanation behind this. Please share a pointer if you have any references.
- SuchAnonMuchWow 3y agoThe main issue with floating point number is that it doesn't act like a ring (https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics)) because of rounding errors. For example the equality x*(y*z) = (x*y)*z doesn't hold because each multiplication introduce small rounding errors. And this kind of equations are required for the exponentiation-by-squaring method (consider for example how x**5 is computed: x**5 = (((x*x)*x)*x)*x) using a naive exponentiation approach, but also x**5 = x*(x*x)*(x*x) = x*(x*x)**2 using the exponentiation-by-squaring method). Integer operations and matrix operations are both rings, so the exponentiation-by-squaring approach works. For floating points, it doesn't give an exact result, but could still be used in practice to get an approximate result. The pow function doesn't use this approach however, because both arguments of the pow function are floating points numbers, and can thus compute things like pow(5, 0.5) = sqrt(5), or even 534.2**12.7. The exponentiation-by-squaring approach works only when the exponent is an integer, so we need other solutions. How exactly the pow function (or other math function like exp, log, cos, ...) are computed is a vast research subject in itself, but if you are interested, the Handbook of Floating-Point Arithmetic (https://perso.ens-lyon.fr/jean-michel.muller/Handbook.html https://perso.ens-lyon.fr/jean-michel.muller/Handbook.html) is both a good introduction to the domain (and the problems associated with the finite precision of floating point number), and provides a lot of techniques to work around or minimize the rounding errors that happens when manipulating floating point numbers.
- wrsh07 3y agoPlease do look at the results of taking that matrix to different powers: https://www.wolframalpha.com/input?i=%5B%5B1%2C+1%5D%2C+%5B1%2C+0%5D%5D%5E5 https://www.wolframalpha.com/input?i=%5B%5B1%2C+1%5D%2C+%5B1... What is this matrix doing? When you left multiply it, you're summing the elements of the left column and putting them in the top left (next fib number). Then you're moving the current number to bottom left (and top right). Incidentally, you move the previous to bottom right. That's interesting!! It's very simple
- abhi9u 3y agoYes, indeed. If you see the thirty three miniatures book, it gives the matrix exponentiation formula for computing Fibonacci numbers, without any explanation behind it. To write the article, I tried to figure out ways it can be explained. And this pattern you suggested shows up nicely even when you express successive Fibonacci numbers in terms of the base cases F0 and F1. Which ultimately lead me to realize, the coefficients are the elements of the matrix.
- __rito__ 3y agoWell, 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 the core. I have been meaning to write it up, but dealing with a bad flu. The closed form leads to approximation errors. I tried Julia, Numpy, Numba, Jax, Rust, but integer overflows are there in any parallelized approach. The naive implementation with LRU caching is the fastest and most reliable so far. I am surely missing something, you can actually use some things to overcome integer overflows, right? I hoped to see those in this article, but they were simply not there. Can anyone else help? Even UInt128 is not enough for 1500th Fibonacci number. The upside of Rust, is that it doesn't fail silently. The compiler is really helpful. Jax, Julia, Numpy confidently give wrong answers. Only way to get the feel is to eyeball a bunch of entries and check for negative numbers. Very easy to spot overflows when you are at, say, 1600th fibonacci, but one can feel confident on wrong answers on smaller numbers.
- alpaca128 3y agoCalculation of such large numbers are usually handled by BigInt libraries that are more or less only limited by memory. In Rust that would be the uint crate.
- abhi9u 3y agoPython 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.
- gs17 3y ago> 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 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.
- g0xA52A2A 3y agoReminds me of similar post with some nice visualisations https://ianthehenry.com/posts/fibonacci/ https://ianthehenry.com/posts/fibonacci/ https://news.ycombinator.com/item?id=36942033 https://news.ycombinator.com/item?id=36942033
- abhi9u 3y agoThat's a work of art. Amazing
- Avshalom 3y agoA (i think) related trick: https://kukuruku.co/hub/algorithms/using-the-quick-raise-of-matrices-to-power-to-write-a-very-fast-interpreter-of-a-simple-programming-language https://kukuruku.co/hub/algorithms/using-the-quick-raise-of-... https://news.ycombinator.com/item?id=8799088 https://news.ycombinator.com/item?id=8799088
- abhi9u 3y agoVery cool. Thanks for sharing.
- kmill 3y agoWe essentially implemented this matrix version in Lean/mathlib to both compute the fibonacci number and generate an efficient proof for the calculation. https://github.com/leanprover-community/mathlib4/blob/master/Mathlib/Tactic/NormNum/NatFib.lean https://github.com/leanprover-community/mathlib4/blob/master... In practice this isn't very useful (the definition of Nat.fib unfolds quick enough and concrete large fibonacci numbers don't often appear in proofs) but still it shaves a bit of time off the calculation and the proof verification.
- cfen 3y agoWhy is there no mention of a generating function approach to derive the analytical form?
- cfen 3y agoWhy is there no mention of using a generating function approach to calculate the analytical function?
- abhi9u 3y agoKnuth shows that technique in TAOCP, vol-1. It was on the longer side and I didn't want to reproduce it in the interest of space and time. I was more focused on the matrix form.
- toolslive 3y agoHm, no mention of Binet or Bernoulli?
- asdftemp 3y agoI really like this analysis, which also discusses the “fast doubling” method: https://extratricky.com/blog/fibonacci-complexity https://extratricky.com/blog/fibonacci-complexity it points out that the bit complexity of the traditional algorithm is actually quadratic. and apparently, restricted to fixed width integers, there is a constant time method.
- gjm11 3y agoThere's less to the "constant time method" thing than meets the eye. If you work modulo M for some fixed M, then the Fibonacci sequence is periodic with period at most M^2 (because if two consecutive numbers are known, so is the whole rest of the sequence), which is a constant. Therefore, for any particular M, you can just write down the at-most-M^2 repeating sequence and what the actual period is (call that p), and then for any n the algorithm goes: reduce n mod p, and then look up the result in your big lookup table. (Actually, this isn't constant-time, because if n is large then reducing it mod p isn't constant-time. For that matter, no algorithm can possibly be constant-time, because unless you pick a modulus for which the period is a power of 2 you always need to look at all the bits of n.)
- vitus 3y agoThe only logarithmic algorithm here is fib_closed_form because floating-point multiplication is a fixed-cost operation (and yields a progressively imprecise result, as other commenters have pointed out). The other approaches use arbitrary precision integers, as you've noted, so additions and multiplications are not actually fixed-cost, but scale with the number of digits you're operating on (addition scales linearly; multiplication in Python uses Karatsuba for sufficiently large N, so it scales like n^1.58). In fact, you can't get a sublinear result with a lossless approach, since the number of digits in Fib(n) scales linearly with n, and so you need O(n) operations to just write out the digits. This is pretty straightforward to explain with the closed-form solution: Fib(n) is roughly 1.618^n / 2.236; by taking the binary logarithm, you can see this requires about 0.7n bits to represent. (Equivalently, 0.2n decimal digits.)
- zschoche 3y agoNit: 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.
- djmips 3y agoSo 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)
- emmender1 3y agoloved this article thanks ! do folks actually read knuth ? i thought his tomes were meant only for bookshelves -lol- -sarcasm-
- abhi9u 3y agoThank you (author here). I don't read TAOCP. I have read first few chapters of volume-1 so I am familiar with the notation and some MIX syntax. But while writing this article, I just opened up specific topics, such as computing Fibonacci numbers in volume-1, or evaluating powers in volume-2 and I managed to understand it. Sometimes you may find back references, such as when discussing Fibonacci numbers, he references Euclid's algorithm and you may have to go back and check it out, or ignore it (depends on the context). So I believe you don't necessarily need to read from cover to the end; you can browse it based on your interest.