[jfarmer]

I 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/

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

(Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)

[abhi9u]

Nice! Thank you for sharing.