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

[Mark Dickinson]

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

The patch looks good.  Just one issue: I think the overflow check for num_operands * last_bit is bogus.  It's possible for the product to overflow and still end up being less than num_operands.  How about:

if (num_operands <= BITS_IN_LONG && num_operands * last_m_bit <= BITS_IN_LONG) ...

instead?  If num_operands <= BITS_IN_LONG then there's no danger of overflow in the multiplication, and if num_operands > BITS_IN_LONG then the second test will certainly fail.

Apart from that, and some very minor style issues (e.g., please put the body of an if statement on the following line;  I don't think this is codified in PEP7, but it seems to be the prevailing style in the Python codebase) I think the patch is good to go.

[Alexander]
"... benefit from redefining partial_product to be product(2*i+1 for i in range(start, stop))"

You mean rewriting to use half-open intervals [start, stop) rather than closed intervals?  In which case I agree it would look slightly cleaner that way, but I don't have particularly strong feelings on the issue.  I'll leave it up to Daniel whether he wants to change this or not.


"I would also reconsider the decision of using iterative outer loop."

I actually prefer the iterative version, perhaps out of a Python-bred aversion to recursion (in languages where the frames end up on the stack, anyway).  The bit_length calculation doesn't seem like a terrible price to pay to me.  Again, I leave this up to Daniel.


Marking this as accepted:  Daniel, if you like I can apply the overflow check change suggested above and the minor style fixes and apply this;  or if you want to go another round and produce a third patch, that's fine too.  Let me know.

(N.B.  If you do produce another patch, please name it something different and don't remove the earlier version---removing the earlier patch versions makes life harder for anyone trying to follow this issue.)

----------
resolution:  -> accepted

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