3 ms·
what if you use the closed-form answer, but without any floating-point or other approximations i mean it all comes out to an integer in the end, all the radica
by kragen 3y ago
what if you use the closed-form answer, but without any floating-point or other approximations
i mean it all comes out to an integer in the end, all the radicals cancel
i see tromp already suggested a form of this
- abhi9u 3y agoBut 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.
- dietrichepp 3y ago> what if you use the closed-form answer, but without any floating-point or other approximations You can use a field extension here, ℚ(√5), to represent your numbers. The numbers would be represented as pairs, (a,b), which represents the number a+b√5. You can see for yourself that this set is closed under addition and multiplication. But when you try to implement code that computes exponents with this representation, you’re probably going to fall back to the old “repeated squaring” trick. But that’s how you calculate exponents with your matrix representation anyway—and you can note that the matrix powers (for this matrix) always take the form | a b | | 0 a | So you can represent these matrixes as (a,b) pairs anyway. We are right back where we started—our state is represented as a pair of numbers, and we use repeated squaring to calculate an exponent. Sometimes these different ideas for representing the problem give us new insight or new algorithms, and sometimes it turns out to be a new perspective on the same piece of code.