speedup help update

[Damien R. Sullivan]

On Mon, Mar 03, 2003 at 04:59:21PM -0800, Hal Daume III wrote:

> comb m n = fact m `div` (fact n * fact (m-n))

This was the biggest help, 33 seconds instead of my original 43.  fact is the
big consumer now, and I think cries out for being arrayed, especially as it
gets used a lot elsewhere too.

> If that doesn't speed it up enouch, you can of course cache fact m in your
> computation and do something like:
> 
> sumbn n = sum [ bournoulli i * fm `div` (fn * fact (m-n)) | i <- [0..n-1]]
>   where fm = fact m
>         fn = fact n

I'm not sure what this is doing.  i has to be in the comb part.

> From there, you should probably look at arrays if you can bound n.

Bound at compile time or at some early point in run time?  The program's
behavior is determined by command line arguments, and filling an array with n
factorials would be perfectly appropriate.

I'm sorry to report that the other suggestions didn't help much.  Andrew
Rock's took 80 seconds.  Andrew Bromage's did gain a slight improvement --
41 seconds instead of 43.  If I replace the factorial in
    in  productRange (i+1) j `div` factorial j
with my own fact then it goes to 37 seconds.  But that's still more time than
Hal's simple use of Integers.

Top 3 functions of the version with Hal's code are:
fact                           Main                  28.5    0.0
comb                           Main                  21.8    9.7
sumbn                          Main                  10.7   16.4

Time to look at arrays, finally.

-xx- Damien X-)