speedup help

[Hal Daume III]

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
>