Haskell: Fibonacci Big Number

fibonacci.hs

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.md

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

If you annotate fibN' like so fibN' :: Integer -> Integer and compile with -O2 the compiler can do some nice optimizations.

raichoo@amy:fib» time -p ./fib
[0,1,1,2,3,5,8,13,21,34]
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
104494
real 1.04
user 1.02
sys 0.01

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 :)

Thanks, that really made a difference.

I'm glad you found this useful ^^