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 * f
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 di
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 produc
Hi Damien,
| 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 functi
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 tr
| 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 qu
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 throug
On Thu, Mar 06, 2003 at 09:23:44PM -0600, Bill Wood wrote:
> I couldn't get getCPUTime (from module CPUTime) to work for me; if
Yeah, I had the same problem -- it would just return ten million or some other
number, consistently. Use of getClockTime and diffClockTimes didn't help
either.
> anyon
. . .
> 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.)
Oleg
> 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 3000. I monito
. . .
>
> > 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 be
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\
518130533026045150594816676476469224548430690874860242714680177615
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.
I would like to say that programming this project (calculate the
Euler-Mascheroni constant to as many digits as possible in a minute) in
Haskell has been fairly pleasant overall. The startup time was a bit oogy
-- ocaml was faster to get a working program -- and ghc's compilation time
continues to
G'day all.
On Mon, Mar 03, 2003 at 09:53:24PM -0500, Damien R. Sullivan wrote:
> Time to look at arrays, finally.
This might help:
http://haskell.org/wiki/wiki?MemoisingCafs
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTE
18 matches
Mail list logo
