speedup help

[Damien R. Sullivan]

On Mon, Mar 03, 2003 at 08:46:22PM -0800, Mark P Jones wrote:

>  pascal :: [[Integer]]
>  pascal  = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
> 
>  comb    :: Int -> Int -> Integer
>  comb n m = pascal !! n !! m

> In that case, you can take further advantage of using Pascal's triangle
> by recognizing that numbers of the form (comb (n+1) i) are just the
> entries in the (n+1)th row.  (All but the last two, for reasons I
> don't understand ... did you possibly want [0..n+1]?)  So we get the

No, the sum for a Bernoulli number is a combination times another Bernoulli
number from 0 to n-1.  Hard to have B_n depend on B_n.  At least in a nice
recurrence...

>   sumbn n = sum [ bernoulli i * fromIntegral c
>                 | (i,c) <- zip [0..n-1] (pascal!!(n+1)) ]

This code as is takes about 23 seconds, comparable to the 22 seconds of
factorial with array (hardcoded, since I can't get it dynamically in a pretty
fashion.)  If I turned pascal into arrays it might be even faster.  I'd have
to change something though, right, zipWith wouldn't work with arrays?

> Actually, I prefer the following version that introduces an explicit
> dot product operator:
> 
>   sumbn n = take n (map bernoulli [0..]) `dot` (pascal!!(n+1))
>   dot xs ys = sum (zipWith (*) xs ys)

This needed some modification, since bernoulli returns Rationals, so I had
zipWith use a special mult function.  It just took 25 seconds.

> slower, I thought these definitions were interesting and different
> enough to justify sharing ...

Hey, you're even faster too!  At least for messing with comb.

Aaron Denney, to his credit, had a pretty similar idea a week ago, but I
didn't get what he was talking about then.  Newbies like code they can paste
in. :)

Thanks!

-xx- Damien X-)