speedup help
Hal Daume III
hdaume@ISI.EDU
Mon, 3 Mar 2003 16:59:21 -0800 (PST)
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 * fact (m-n)) | i <- [0..n-1]]
where fm = fact m
fn = fact n
it is possible that the compiler is inlining the call the comb, in which
case this has already been done for you. hard to say for sure. putting
'{-# INLINE comb #-}' might help a lot.
>From there, you should probably look at arrays if you can bound n.
--
Hal Daume III | hdaume@isi.edu
"Arrest this man, he talks in maths." | www.isi.edu/~hdaume
On Mon, 3 Mar 2003, 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 a memoized factorial function. It's not perfectly memoized,
> though; I use lists, since that's easier by default. They should be arrays,
> and possibly just changing that would speed comb up a lot. (Comb is currently
> 40% of runtime, fact is 23%.) But I think it should be possible to speed up
> comb itself, too.
>
> comb is only called from here:
> sumbn n = sum [ bernoulli i * fromIntegral(comb (n+1) i) | i <- [0 .. n-1] ]
>
>
> Here was one try:
>
> fcomb :: Integer -> Integer -> Integer
> fcomb m 0 = 1
> fcomb m n = res
> where
> res = last * (m-n+1) `div` n
> last = res
>
> except, obviously, this doesn't work. I hope it's clear what I'm trying to
> do, or what I would be in a more imperative language -- in C I'd probably have
> some static variable in fcomb. I figure monads are needed, but I've been
> unable to figure them out enough to apply them here. Will the monadism
> propagate all the way up and require changing lots of function types? Bleah.
> I'm using ghc, can I sneak some mutable in here instead?
>
> Any advice? Also on using arrays, where my parameters come off the command
> line. I imagine in C++ I'd just precompute a bunch of tables and then just
> use those values in the actual algorithm.
>
> Thanks!
>
> -xx- Damien X-)
>
> (if you're curious, this is for a class, but not a class on using Haskell. I
> chose to use Haskell for this assignment after ghc -O, to my surprise,
> outperformed ocaml. I suspect GMP deserves the real credit, but hey.)
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>