Skip to content

Instantly share code, notes, and snippets.

@mjdominus

mjdominus/fib.hs

Created March 28, 2011 17:54
Show Gist options
  • Save mjdominus/890925 to your computer and use it in GitHub Desktop.
Save mjdominus/890925 to your computer and use it in GitHub Desktop.
Download ZIP
fibonacci identity
Raw
fib.hs
choose _ 0 = 1
choose 0 _ = 0
choose n k = choose (n-1) (k-1) * n `div` k
pow n 0 = 1
pow n k = n * pow n (k-1)
fib n = theSum `div` pow2
where theSum = sum [ (choose n (2*k+1)) * (pow 5 k) |
k <- [0 .. div (n-1) 2] ]
pow2 = pow 2 (n-1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment