[Haskell-cafe] speeding up fibonacci with memoizing

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Mon Feb 19 04:36:20 EST 2007

Stefan O'Rear wrote:
> Prior art trumps all.  (by a few %)  granted it doesn't do much memoizing anymore :)
> gs > ajb > f > d > u, it, z > s > n


Nice. I took the opportunity to polish my generic linear recurrence
module somewhat and test its speed. It does quite well I think:


and defining

> import qualified LinRec as L
> -- generic linear recurrence generator
> genfib = L.get [1,1] [0,1]

I get:

# ./t.sh gen 50000000
11.65user 0.06system 0:11.71elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+17092minor)pagefaults 0swaps
# ./t.sh gs 50000000
4.67user 0.06system 0:04.79elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+11746minor)pagefaults 0swaps

for a slowdown of about 2.5.


More information about the Haskell-Cafe mailing list