Fast fibonacci algorithm

fibonacci.hs

module Main (main) where

import System.Environment (getArgs)

-- | Matrix multiplication
(×) :: Num a => (a, a, a, a) -> (a, a, a, a) -> (a, a, a, a)
(a11, a12, a21, a22) × (b11, b12, b21, b22) =
  (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22,
   a21 * b11 + a22 * b21, a21 * b12 + a22 * b22)

-- | Matrix powers
(××) :: (Num a, Integral b) => (a, a, a, a) -> b -> (a, a, a, a)
m ×× 1 = m
m ×× n
  | even n    = let m' = m ×× (n `div` 2) in m' × m'
  | otherwise = m ×× (n - 1) × m

-- | The 'n'th fibonacci number
fib :: (Integral a, Num b) => a -> b
fib n = (\(_, x, _, _) -> x) $ (0, 1, 1, 1) ×× n

-- | Specialize function for 'Integer' (only a type change)
fibInteger :: Integer -> Integer
fibInteger = fib

main :: IO ()
main = print . fibInteger . read . head =<< getArgs