Now that I've looked at the patch properly:

I'm +1 on including some version of this patch.  At the time that the original math.factorial went in (see issue 2138) we were hurrying a bit to get it in before the first 2.6 beta, so ended up with a simple implementation, with the understanding (I think) that it could be improved later.

It looks like you and Alexander are doing a great job of hammering out the fine detail;  I only have a few comments at this stage.  I predict that you're not going to like the first one ;-).  The others are just technical issues.

(1) In the interests of simplicity, please could we lose the 'long' optimization in factorial_part_product?  That is, get rid of the if (m == n+2) branch, and just let that case recurse normally---which means that we end up calling PyNumber_Multiply in some cases instead of doing a C long by C long multiplication.  Then we can get rid of multiply_cutoff entirely.  I'm +1 on the improved algorithm, and I realize that the optimization does have an effect (some unscientific tests showed me a 18% speed increase in typical cases) but for me this optimization goes past the simplicity/speed tradeoff.  There's always the option of adding something like this back in later, once the new algorithm's gone in.

(2) You're missing a Py_DECREF(part) in factorial_loop, so factorial(n) leaks references (for n > 12).

(3) The line "k = (n + m) / 2;" in factorial_part_product invokes undefined behaviour (from signed overflow) if n and m are large.  We're not going to get meaningful results in this case anyway, but UB should be avoided if at all possible.  Perhaps rewrite this as "k = n + (m - n) / 2;"?

(4) And please do restore the PyLong_FromDouble line in the main routine, rather than using a C double-to-long cast.  The direct conversion again leads to undefined behaviour for large doubles (cf. C99 6.3.1.4,p2).