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