Skip to content

Instantly share code, notes, and snippets.

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