gistfile1.hs

 20 fib :: (Num a, Integral a) => a -> Integer                                |@
 19 fib  = snd . fastfib                                                      |@
 18     where   fastfib :: (Num a, Integral a) => a -> (Integer, Integer)     |@
 17             fastfib 0               = (0, 0)                              |@
 16             fastfib 1               = (0, 1)                              |@
 15             fastfib n                                                     |@
 14                 | n `mod` 2 == 1    = ((a + c) * b, (c*c) + (b*b))        |@
 13                 | otherwise         = ((a*a) + (b*b), (a + c) * b)        |@
 12                 where d = fastfib (n `div` 2)                             |@
 11                       a = fst d                                           |@
 10                       b = snd d                                           |@
  9                       c = a + b                                           |<
  8 main :: IO()                                                              | 
  7 main = do                                                                 |@
  6     before <- getCPUTime                                                  |@
  5     return $! fib 5000000 -- $! forces evaluation                         |@
  4     after <- getCPUTime                                                   |@
  3     putStrLn $ show $ (after-before) `div` 10^9