[Haskell-cafe] speeding up fibonacci with memoizing

[Felipe Almeida Lessa]

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)

How about this:
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
  let n = read arg
  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.