Fib.hs

fib' :: (Integer, Integer) -> (Integer, Integer) -> Integer -> Integer
fib' (p, q) (x0, x1) n = go n (p, q) (x0, x1)
  where
    go 0 (p, q) (x0, x1) = x0
    go n (p, q) (x0, x1) = if odd then go (n-1) (p, q) $! step (p, q) (x0, x1)
                           else go n' (p', q') (x0, x1)
      where
        (n', b) = n `divMod` 2
        odd = not (b == 0)

        p' = p * p + q * q
        q' = 2 * p * q + q * q

    step (p, q) (x0, x1) = let x0' = p * x0 + q * x1
                               x1' = q * x0 + (p+q) * x1
                           in x0' `seq` x1' `seq` (x0', x1')
                           
fib n | n >= 0 = fib' (0, 1) (0, 1) n
      | otherwise = fib' (0, -1) (1, 0) (negate n + 1)