Skip to content

Instantly share code, notes, and snippets.

@arianvp
Created September 22, 2012 22:36
Show Gist options
  • Save arianvp/3768092 to your computer and use it in GitHub Desktop.
Save arianvp/3768092 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment