Skip to content

Instantly share code, notes, and snippets.

@callerobertsson
Last active November 22, 2017 17:00
Show Gist options
  • Save callerobertsson/38edd025431a74b0441a to your computer and use it in GitHub Desktop.
Save callerobertsson/38edd025431a74b0441a to your computer and use it in GitHub Desktop.
Haskell: Fibonacci Big Number
module Main where
main = do
print $ map fibN' [1..10]
print $ fibN' 1001
print $ length $ show $ fibN' 500000
fibN' 1 = 0
fibN' 2 = 1
fibN' n = iter 0 1 n where
iter a b 3 = a + b
iter a b n = iter b (a + b) (n - 1)

Result

A bit slower than the Golang version but a bit more compact and readable code.

$ ghc fibonacci.hs && time ./fibonacci
[0,1,1,2,3,5,8,13,21,34]
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
104494

real    0m10.660s
user    0m10.571s
sys     0m0.085s
@raichoo
Copy link

raichoo commented Dec 6, 2015

If you care about the generality of fibN' you can add the following pragma {-# INLINABLE fibN' #-} which generates a specialized version depending on the call site. It yields the same performance as the manually specialized version :)

@callerobertsson
Copy link
Author

Thanks, that really made a difference.

@raichoo
Copy link

raichoo commented Dec 7, 2015

I'm glad you found this useful ^^

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment