Fib.hs

import Data.Ratio

-- Q5 = Q(sqrt(5))
data Q5 = Q5 Rational Rational deriving (Show, Eq)

instance Num Q5 where
  fromInteger n = Q5 (fromInteger n) 0
  Q5 a b + Q5 c d = Q5 (a + c) (b + d)
  Q5 a b * Q5 c d = Q5 (a * c + 5 * b * d) (a * d + b * c)
  negate (Q5 a b) = Q5 (-a) (-b)

instance Fractional Q5 where
  recip (Q5 a b) = Q5 (a / norm) (-b / norm)
    where
      norm = a*a - 5*b*b

root5 = Q5 0 1

phi = (1 + root5)/2
psi = (1 - root5)/2

fib :: Integer -> Q5
fib n = (phi^n - psi^n)/root5

fib' :: Integer -> Integer
fib' n = numerator a where Q5 a b = fib n