Two Efficient Fibonacci Algorithms

Fibs.hs

data Mat a = M !a !a !a !a deriving (Eq, Read, Show)

-- 2x2 matrix multiplication
matMult :: Num a => Mat a -> Mat a -> Mat a
matMult (M x11 x12 x21 x22) (M y11 y12 y21 y22) = M z11 z12 z21 z22
  where
    z11 = x11*y11 + x12*y21
    z12 = x11*y12 + x12*y22
    z21 = x21*y11 + x22*y21
    z22 = x21*y12 + x22*y22

-- 2x2 matrix (non-negative) exponentiation
matExp :: Num a => Mat a -> Integer -> Mat a
matExp m n = iter (M 1 0 0 1) m n
  where
    iter acc b i
      | i == 0    = acc
      | even i    = iter acc (matMult b b) (i `div` 2)
      | otherwise = iter (matMult acc b) b (i - 1)

-- log-time constant memory fibonacci numbers
fib :: Integer -> Integer
fib n = (\(M _ x _ _) -> x) (matExp (M 1 1 1 0) n)

-- linear-time memoized fibonacci numbers
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)