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

[Daniel Stutzbach]

Daniel Stutzbach <daniel at stutzbachenterprises.com> added the comment:

Speaking of getting side-tracked, I didn't see an answer to a question I asked earlier.  I'd like to get some feedback before I proceed with revising the patch.

For the find-last-set-bit (to replace log2) and count-set-bits operations, would it be worthwhile to create a pybits.h and .c that defines _Py_FindLastSetBit and _Py_CountSetBits? (with appropriate logic in the .h and configure.in to use system/compiler versions if available)

There are already two implementations of find-last-set-bit in Python:
bits_in_digit() in Objects/longobject.c and hi0bits() in Python/dtoa.c, which I could consolidate.

Alternately, I could just add static functions to mathmodule.c with the simplest possible implementation (they're only called once per factorial, so the performance impact is minimal).

----------

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