Fast algorithms for computing the factorial

Question

I found this page describing a number of algorithms for computing the factorial. Unfortunately, the explanations are terse and I don't feel like sifting through line after line of source code to understand the basic principles behind the algorithms.

Can anybody point me to more detailed descriptions of these (or other fast) algorithms for computing the factorial?

Edit: This page describes the method of prime factorization, the technique common to all of the best-performing factorial algorithms. It also contains some nice example code in Python. The author links to a description of binary splitting and references an article in the Journal of Algorithms ("On the Complexity of Calculating Factorials") that looks promising, if I could only get my hands on it.

Solution 1

Check out this paper (PDF link) by Richard Fateman. The code samples are in Lisp, in but in any event, much of the secret boils down to minimizing the number of bignum (arbitrary precision integer) calculations you have to do.

Naturally, if you don't need/have bignums, it's trivial; either a lookup table or a simple loop will be fine.

EDIT: If you can use an approximate answer, you can either compute the logarithm of the factorial directly by summing log(k) for k = 2 ... n, or by using the venerable Stirling approximation. You want to work with the logarithm wherever possible to avoid overflow; in particular, a naive application of Stirling's approximation will overflow in a lot of places where it doesn't have to.

Solution 2

There is also another method. This method is detailed here that halves the amount of multiplication for a little bit of addition and subtraction. You probably want the first method shown, and the second method shown is an interesting read if you can understand it.

Comments

[Rooke]

If your factorial is big, and you want an approximation, don't forget Stirling's approximation. I noticed it wasn't mentioned in that page. en.wikipedia.org/wiki/Stirling%27s_approximation

[ThisSuitIsBlackNot]

@Rooke: I was looking to compute large factorials exactly...perhaps I should have been clearer in my question. Thanks for the suggestion though!

[Spektre]

You can also try mine Fast exact bigint factorial

[ThisSuitIsBlackNot]

+1: That paper is very helpful (although my Lisp is a little rusty). Unfortunately, it looks like Luschny is the go-to guy for more complex algorithms, so I may be stuck reading through his source code.

[Mujtaba Aldebes]

Would be much readable and faster to use the built in function math.factorial(x)