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

[Daniel Stutzbach]

Daniel Stutzbach <daniel at stutzbachenterprises.com> added the comment:

On Fri, May 14, 2010 at 3:25 PM, Mark Dickinson <report at bugs.python.org> wrote:
> 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:

You're right; I'm not sure what I was thinking. (actually, I'm pretty
sure I was thinking about addition ;) )

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

Yes, that looks good.

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

That would be great. :)

With regards to find_last_set_bit, I understand where you're coming
from, but I'm following the convention of ffs/fls and also
bits_in_digit() from longobject.c.  I'd like to keep them
interchangeable, in case they're consolidated at some point in the
future.  If you want to rename the function, that's fine with me.

FWIW, I think the MSB=0th people are all electrical engineers.  If
you're serializing down to bits and the MSB is the first (0th) bit off
the wire, it makes sense in that context.

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

Good to know.  I'll keep that in mind going forward.

Thanks to both of you for the rigorous review.  This was a fun patch
to work on. :-)

----------

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