Although the original post wasn't about it, here's a version of exact arithmetic in the field extension containing phi. I wrote in Ruby a long time ago: https:

Although the original post wasn't about it, here's a version of exact arithmetic in the field extension containing phi. I wrote in Ruby a long time ago: https://gist.github.com/jfarmer/82500f2b52c540df5fbc https://gist.github.com/jfarmer/82500f2b52c540df5fbc You still have to implement the exponentiation algorithm, so you're never really going to get O(1). This is better than O(n), though. With those things implemented it becomes def fib_phi(n) ((PhiRational.new(0,1)**n - PhiRational.new(1,-1)**n)/PhiRational.new(-1, 2)).a.to_i end which is the explicit formula. I'd love to see the same thing in Haskell, which I imagine would look less crazy.