# speedup help

**Damien R. Sullivan
**
dasulliv@cs.indiana.edu

*Tue, 4 Mar 2003 15:45:51 -0500*

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-)