You might be interested in a solution I posted: http://www.codewars.com/dojo/katas/reviews/52255487906b0c1733000452/groups/522cd249900801524d000063

It starts by implementing "exact arithmetic" in the field extension ℚ(𝜑) = {a + b𝜑 | a,b ∈ ℚ}, where ℚ are the rational numbers and 𝜑 is the golden ratio. Since

fib(n) = [𝜑 ⁿ - (1-𝜑) ⁿ]/(2𝜑 - 1)

we can implement the "explicit formula" by implementing an algorithm for exponentiation in ℚ(𝜑) .

In the code, the representation works as follows

PhiRational.new(a,b)  # a + b𝜑
PhiRational.new(0,1) # 𝜑
# etc.

This makes me want to play Master of Magic again...

Am I correct that this would be a nice starter for some Haskell / functional programming stuff? I never got my hands dirty on these things, but one day I'll start, promised.

JHoffner, did you get my suggestion of adding Haskell to the mix? Or whatever is the craze in functional programming this year?

Ho-ly-cow

Man you must love your oxford commas.