Bill Wood wrote:
I think I got the right results for B_3000: [...]
Mathematica 4.1 computes B_3000 as follows:
In[1]:= BernoulliB[3000]
Out[1]=
-28919392162925009628147618267854828678617917853903846822112332719169192942048\
. . .
Oleg's blew the heap at 847; mine valiantly struggled on 'til it blew
the heap at 1910.
Hmm, I managed to compute bernoulli 2000 and even bernoulli 3000. The
code is included. It took 7 minutes (2GHZ Pentium IV, 1GB memory) to
compute bernoulli 2000 and 33 minutes for bernoulli
| comb is only called from here:
| sumbn n = sum [ bernoulli i * fromIntegral(comb (n+1) i) | i
| - [0 .. n-1] ]
Probably I misunderstand what bernoulli i stands for. If it is meant
Bernoulli number B_i,
http://mathworld.wolfram.com/BernoulliNumber.html
then the above expression is
Oleg has a very interesting approach; in particular, he avoids
explicit recursion and (most) computing with rationals, while
also replacing the factorials in binary coefficients by using
successive rows of Pascal's triangle. He also skips over the
B_{2k+1}, k 0, which are all 0.
I slogged
. . .
This code seems to compute 'bernoulli 82' in less then a second, in
Hugs (on a 2GHz Pentium IV).
Just a note: I compiled and ran Oleg's and mine for comparison. The
two seem to be of the same complexity, with Oleg's a little faster
(modulo my using wall time; see previous msg.)
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
So, I'm having to calculate 'n choose k' an awful lot. At the moment I've got
this:
comb :: Integer - Integer - Integer
comb m 0 = 1
comb m n = (numerator(toRational (fact m) / toRational (fact n * fact (m-n
where fact is a memoized factorial function. It's not perfectly memoized,
I think you would get a big speed-up if you got rid of all the rational
stuff and just used:
comb m n = fact m `div` (fact n * fact (m-n))
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 *
On Tuesday, March 4, 2003, at 10:26 AM, Damien R. Sullivan wrote:
So, I'm having to calculate 'n choose k' an awful lot. At the moment
I've got
this:
comb :: Integer - Integer - Integer
comb m 0 = 1
comb m n = (numerator(toRational (fact m) / toRational (fact n * fact
(m-n
where fact is
G'day all.
On Mon, Mar 03, 2003 at 04:59:21PM -0800, Hal Daume III wrote:
I think you would get a big speed-up if you got rid of all the rational
stuff and just used:
comb m n = fact m `div` (fact n * fact (m-n))
Or, even better, if you didn't multiply stuff that you're just going
to
I have no idea if the following is faster or not (I suspect not), but
it is certainly easier to read:
n `choose` k = (n `permute` k) `div` (fact k)
n `permute` k = product [(n-k+1) .. n]
fact n = product [1 .. n]
mike
--
mike castleman / [EMAIL PROTECTED] / http://mlcastle.net
aolim: mlcastle
On Tue, Mar 04, 2003 at 12:25:01PM +1100, Andrew J Bromage wrote:
Or, even better, if you didn't multiply stuff that you're just going
to divide out in the first place.
I had thought of that before, and used a simple
comb m n = product [m, m-1 .. m-n+1] / fact (m-n)
but the unmemoized product
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.
13 matches
Mail list logo
