Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A linear algebra trick for computing Fibonacci numbers fast

codeconfessions.substack.com

Post reply on HN
Print view View original

31–40 of 76 posts

Re: A linear algebra trick for computing Fibonacci numbers fast

#31

Post by abhi9u »

wrsh07 wrote: post #24

Please 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... 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…

Yes, 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.

Re: A linear algebra trick for computing Fibonacci numbers fast

#32

Post by kmill »

We 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...

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.

Re: A linear algebra trick for computing Fibonacci numbers fast

#35

Post by SuchAnonMuchWow »

abhi9u wrote: post #25
SuchAnonMuchWow wrote: post #21

The 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)…

Author 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 exp…

The main issue with floating point number is that it doesn't act like a ring (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) 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.

Re: A linear algebra trick for computing Fibonacci numbers fast

#36

Post by alpaca128 »

__rito__ wrote: post #26

Well, 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…

Calculation 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.

Re: A linear algebra trick for computing Fibonacci numbers fast

#37

Post by abhi9u »

SuchAnonMuchWow wrote: post #35
abhi9u wrote: post #25

Earlier quoted context omitted.

Author 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 exp…

The main issue with floating point number is that it doesn't act like a ring ( 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…

Thank you so much, both for providing more background on exponentiation, and for the reference. :-)

Re: A linear algebra trick for computing Fibonacci numbers fast

#38

Post by abhi9u »

__rito__ wrote: post #26

Well, 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.

Re: A linear algebra trick for computing Fibonacci numbers fast

#40

Post by abhi9u »

cfen wrote: post #34

Why is there no mention of using a generating function approach to calculate the analytical function?

Knuth 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.
Post reply on HN