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
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
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 |
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.
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.
Code winds up looking like:
def fib_phi(n)
((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i
end
(Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)