[issue8692] Use divide-and-conquer for faster factorials

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

> I would expect that for large factorials the performance will be
> determined by the number of long multiplications and the size of
> multiplicands.

Okay, but I don't think we should care about the performance of *really* large factorials for Python.  People who care about every bit of speed in that situation should be using GMP or something similar.  An optimization that only makes a difference for (say) factorial(50000) or higher isn't going to make much difference to most Python users.  Optimizations that speed up, say, factorial(n) for n <= 1000 would seem more valuable.

> The differences between recursive and non-recursive versions are not
> likely to translate well, but the difference (if any) between the
> order of multiplication most likely will.

Perhaps.  But the differences between the various Python versions here are small enough that they could easily be swamped by other factors involved in the Python-to-C translation.

We already have a working C patch here (modulo minor issues), and I'd like to move forward with that patch;  I think this issue discussion is getting a bit side-tracked.

grumpily-yours...

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue8692>
_______________________________________