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

[Alexander Belopolsky]

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

On Tue, May 11, 2010 at 9:07 PM, Daniel Stutzbach
<report at bugs.python.org> wrote:
>
> Daniel Stutzbach <daniel at stutzbachenterprises.com> added the comment:
>
> On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky
> <report at bugs.python.org> wrote:
>> Speaking of micro-optimizations, did you consider a better than naive
>> algorithm for "Count the number of set bits in n" in your patch?
>> ..
> I considered it, but decided to stick with code readability and
> portability.

Speaking of readability, with a separate popcount() function, you can
simply write

nminusnumbits_ob = PyLong_FromLong(n - popcount(n))

and eliminate not only the loop, but also num_bits and tmp variables
from math_factorial()

The popcount function can be defined as a __builtin_popcount on GCC
and your loop otherwise.

>  Counting the number of set bits is only done once per
> factorial, so it's not on the critical path.
>

I agree, performance consideration are completely irrelevant here.

Similarly, while unlikely to improve performance, I would prefer not
to use any bit-trick implementation of ilog2 (in a separate function,
of course) instead of calling floating point log2.  In my head, an
assignment of floating point result to an integer variable always
raises a red flag.

Another readability nit:  for me k % 2 == 0 is a more readable check
for even number than (k & 1) != 1.  Performance-wise the two choices
are the same, and either can be improved by combining k = (n + m) / 2
and k & 1 into one ldiv call.

I have not tried to do it, but my gut feeling is that
factorial_part_product() can benefit from passing semi-open rather
than closed interval.  (Also renaming n and m to start and stop in
this case will help understanding.)

----------

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