Fast Fibonacci

gistfile1.hs

fib :: (Num a, Integral a) => a -> Integer
fib  = snd . fastfib
    where   fastfib :: (Num a, Integral a) => a -> (Integer, Integer)
            fastfib 0               = (0, 0)
            fastfib 1               = (0, 1)
            fastfib n
                | n `mod` 2 == 1    = ((a + c) * b, (c*c) + (b*b))
                | otherwise         = ((a*a) + (b*b), (a + c) * b)
                where d = fastfib (n `div` 2)
                      a = fst d
                      b = snd d
                      c = a + b
main :: IO()
main = putStrLn $ show $ fib 300000