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

[Alexander Belopolsky]

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

Mark, It is always a pleasure to read your algorithm descriptions!

Just a few comments:

- It would be nice if a pure python implementation would make it
somewhere in the code base.  Maybe it can be placed in comments in C
file or added to the test module somehow.

- Please rename arguments to factorial_partial_product() from n, m to
start, stop.   It is confusing enough that n has a different meaning
loop() and partial_product(), but n, m coming in reverse alphabetical
order makes it really hard to follow the code.

- Using n as a variable in the fast loop saves one integer assignment
(likely to be optimized away) at the expense of clarity.    One has to
realize that there is an unconditional return after the loop before
concluding that n is the same in the recursive part.

- "We know that m is the largest number to be multiplied."  Shouldn't
that be m - 2?

- Is find_last_set_bit() the same as bit_length()?  If so, why isn't
it called the same?   I don't want to bikeshed, but seeing
find_last_set_bit makes me wonder if "last" means most or least
significant bit.

- There is a comment line /* r *= inner; */ in factorial_loop() but no
r variable.  Shouldn't that be outer *= inner?

I'll review math_factorial() after reading Daniel's message that just arrived.

----------

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