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

[Alexander Belopolsky]

Alexander Belopolsky <belopolsky at users.sourceforge.net> added the comment:

On Thu, May 13, 2010 at 6:09 PM, Daniel Stutzbach
<report at bugs.python.org> wrote:
..
> 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.

I did not respond because I don't have an answer. :-)  Maybe it is
time to revisit Raymond's reasoning in msg63969 where he argued that
factorial should be an int method because it would benefit from access
to integer implementation details.

He also argued that
"""
Compared to  numbits() and isqrt(), a factorial() method is more basic
in that it is self explanatory and everyone knows what it means by the
time they are in middle school.
"""
nevertheless numbits() aka bit_length() has become an int method, but
factorial landed in math.

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

Since it is unlikely that either factorial() or bit_length() will be
moved from their current location, I would be +1 on creating pybits.
I would give them different names, though.  Popcount seems to be the
most popular name for CountSetBits and instead of FindLastSetBit, a
more common function seems to be nlz, number of leading zeros.  On the
other hand, since  bit_length is already established, maybe
_Py_bit_length_long(long) and (if needed) _Py_bit_length_int(int)
would make sense.

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

How did you find it?!  I hope we'll end up with a better name than that.

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

In the scope of this issue I would say do that.  Pybits proposal seem
to deserve it's own issue.

----------

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