[Haskell-cafe] faster factorial function via FFI?

[David Roundy]

On Mon, Apr 23, 2007 at 01:06:07PM -0500, Dan Drake wrote:
> Hello everyone,

Hi!

> 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.

I'm curious: what is your application? I've never seen one in which
factorials actually need be computed.  In physics, one factorial is
generally divided by another (e.g. for combinatorics), so it's rarely wise
to take the actual factorials.  And to be honest, we usually take the
thermodynamic limit and then use Stirling's approximation.  I guess they
also show up in Taylor expansions, but then we never go far enough for the
factorial to be expensive.

> 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. 

If you really have small numbers and need speed, I'd switch to using Ints.
That'd gain you a lot more than an optimized Integer factorial.
-- 
David Roundy
Department of Physics
Oregon State University
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070423/fd37fb4e/attachment.bin