[Haskell-cafe] faster factorial function via FFI?

Stefan O'Rear stefanor at cox.net
Mon Apr 23 18:22:33 EDT 2007


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


More information about the Haskell-Cafe mailing list