Blazing fast Fibonacci numbers using Monoids
haskellforall.com/2020/04/blazing-fast-fibona...Posted Apr 23, 2020, 9:52 AM UTC
2327
haskellforall.com
How does it compare to a c implementation?
3
c doesn't support arbitrarily large integers unless you use an external library or implement them yourself. so the two aren't directly comparable
11
I don't see how that follows. You can easily compare performance and implementation complexity directly.
5
Only if you use some kind of bigint library in C, otherwise they are doing different things and it would be silly to compare them.
7
ghc is probably using one too (gmp), unless it's built with integer-simple, in which case it will be pretty slow
9
Of course.
1
Okay, so assuming I am using an external library for handling large integers, i mean it doesn’t really matter. The author claims blazingly fast, but in that case it makes sense to know relative to what. I am by no means convinced that it actually fast.
1
it was blazing fast compared to the naive implementations.
5
The squaring trick is interesting, but wouldn't it be faster to diagonalize the matrix first and then just exponentiate the matrix of eigenvalues? Or does that just give us the closed form expression that the author avoids to begin with?
3
yeah, the eigenvalues are the golden number and its reciprocal, so that just gets you back to floating point computations, which we want to avoid
12
Indeed. You can represent the eigenvalues exactly in the form (a + b√5) / c, where a, b, c are integers. When you exponentiate this quadratic surd, you once again come back to the integer matrix method.
1
Blazing fast
Well it's not that fast, since the matrix version does a bunch of calculations twice.
2
Which calculations are you referring to?
3
The matrix stores (and so calculates) F(n) twice, has an F(n - 1) it doesn't need, and calculates F(n) in a suboptimal way.
3
How do you propose the algorithm can be simplified? Everything it computes seems necessary to me. Except, I suppose, for the final round of calculations. But altering that is going to make a minuscule difference.
1
The easiest change would be to remove the repeated F(n) from the matrix. Going further, https://www.nayuki.io/page/fast-fibonacci-algorithms.
6
You can support negative fibonacci, and you don't need 4 numbers, only 2.
This link:
https://www.schoolofhaskell.com/user/edwardk/fibonacci/search
is the fast Fibonacci monoid I wrote a few years back.
The key is that you want to represent 1 degree polynomials of the form aφ+b. We know what φ^2 is, so doing addition and multiplication with that number type is well defined.
Now you can do everything you can do with Num.
4
Could you use the monoid of multiplication in the ring Z[x]/(x^2 - x - 1)?
Edit: Also, with respect to the final round of calculations, remember that Haskell is lazy.
3
Interesting. In our intro to CS course, the "go-to" way of fast Fibonacci number generation is just having a third accumulator variable, which makes it tail-recursive.
fib a b n = fib b (+ a b) (- n 1)
fib a _ 0 = a
Here, fib 0 1 n would produce the nth Fibonacci number. I wonder how this would compare in speed to your solution, since yours seems a fair bit more complex.
1
The blog post solution is much quicker for computing a particular Fibonacci number since, as mentioned, the exponentiation by squaring is O(log(n)) rather than the usual O(n) for an iterative approach. Try both out in ghci with an input of at least six figures. Of course if speed matters the closed-form solution with rounding is the answer.
16
I have always thought that canonical Haskell implementation is
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
7
Ah yeah, that's pretty neat. We only did Haskell as a sort of "functional pseudocode" for Racket, so we didn't end up covering things like zipWith.
2
Interestingly, the set Fibonacci matrices with matrix multiplication forms an abelian group (every element has an inverse, and commutativity holds). It's actually isomorphic to the integers with addition. It would be interesting if the Haskell runtime could take that information to do any optimizations.
Being able to reorder elements might let the compiler make faster code, but at least it would be a lot easier to ask for negative fibonacci numbers. Or the generation of inverses might lead to fewer multiplications when, for example, you want the 127th fibonacci number. That way you could repeat your way up to 128 and then "subtract" 1.
It might take more work/time to "teach" the runtime how to do that, if the compiler isn't intelligent enough.