[Haskell-cafe] speeding up fibonacci with memoizing

[Bertram Felgenhauer]

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

[snip]

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

using
  http://int-e.home.tlink.de/haskell/LinRec.hs

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.

Bertram