Damien R. Sullivan
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 (+) ( ++ row) (row ++ )) 
> 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
> 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
-xx- Damien X-)