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

[Mark Dickinson]

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

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

How about putting them in pymath.c and pymath.h?   Then there's no
need for new files.  There's the possible issue that the two
bit-counting methods operate on different types, though.

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

dtoa.c should be left alone, ideally:  it's currently almost
completely self-contained, and also very close to the original dtoa.c
from David Gay, which makes it easy to incorporate fixes from
upstream.  So it's just Objects/longobject.c that would share the
code.

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

That would work, too.

----------

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