On Mon, Apr 23, 2007 at 01:06:07PM -0500, Dan Drake wrote:
Hello everyone,
I have some code in which the bottleneck is the factorial function. I began by using a naive
fac n = product [1..n]
but it looks like there are faster ways to do it. I could try to look up those faster algorithms and implement them, but I'm guessing that using libgmp's factorial function is the best way to do it. I'm a poor programmer, so I don't trust myself to implement those algorithms properly. Hence I need to use FFI.
...but ghc already uses libgmp for Integers, so shouldn't I be able to somehow call libgmp's factorial function?
Using regular FFI stuff, it looks like this might get complicated, since the function doesn't return one of the usual foreign types, so I'd need to mess around to get the result into an Integer, which is what I need.
Is there an easy way to do this? It might also be faster to use a lookup table, since most of the time I'll be taking factorials of relatively small numbers.
In addition to David's comments, note that there was a huge thread on fast fibonaccis recently, including a FFI fibonacci.. Note that the fastest haskell fibonacci was 3 LoC and only 25% slower than the one in libgmp. http://haskell.org/pipermail/haskell-cafe/2007-February/022647.html Stefan