4 ms·
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
by abhi9u 3y ago
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
- kragen 3y agohmm, maybe? i haven't tried it so i can't be sure, but it's plausible
- kmill 3y agoYes, 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 numbers, but it's pretty neat.
- finite_depth 3y ago[dead]
- jfarmer 3y agoI 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/ 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 performance: https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring (Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)
- abhi9u 3y agoNice! Thank you for sharing.