# [Haskell-cafe] speeding up fibonacci with memoizing

Felipe Almeida Lessa felipe.lessa at gmail.com
Sun Feb 18 07:38:49 EST 2007

```On 2/18/07, Thomas Hartman <tphyahoo at gmail.com> wrote:
> -- versus, try memoized_fibs !! 10000
> memoized_fibs = map memoized_fib [1..]
> memoized_fib = ((map fib' [0 ..]) !!)
>     where
>       fib' 0 = 0
>       fib' 1 = 1
>       fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)

zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)]
zip_fib = (!!) zip_fibs

A naïve performance test:

----------------------------------------------------------------
module Main (main) where

import System (getArgs)

zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)]
zip_fib = (!!) zip_fibs

memoized_fibs = map memoized_fib [1..]
memoized_fib = ((map fib' [0 ..]) !!)
where
fib' 0 = 0
fib' 1 = 1
fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)

main = do
[func,arg] <- getArgs
case func of
"zip_fib" -> do
putStrLn \$ "Using 'zip_fib' to calculate fib of " ++ arg
putStrLn \$ " -> " ++ show (zip_fib n)
"memoized_fib" -> do
putStrLn \$ "Using 'memoized_fib' to calculate fib of " ++ arg
putStrLn \$ " -> " ++ show (memoized_fibs !! n)
----------------------------------------------------------------

\$ rm *.o

\$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.4.2

\$ ghc -O fib.hs

\$ time ./a.out zip_fib 20000
Using 'zip_fib' to calculate fib of 20000
-> 25311623237323612422[...]39857683971213093125

real    0m0.140s
user    0m0.106s
sys     0m0.001s

\$ time ./a.out memoized_fib 20000
Using 'memoized_fib' to calculate fib of 20000
-> 25311623237323612422[...]39857683971213093125

real    0m30.787s
user    0m29.509s
sys     0m0.156s

\$ time ./a.out zip_fib 200000
Using 'zip_fib' to calculate fib of 200000
-> 15085683557988938992[...]52246259408175853125
real    0m24.790s
user    0m23.649s
sys     0m0.159s

No, I *won't* try './a.out memoized_fib 200000'  ;-).

--
Felipe.
```