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

[Daniel Stutzbach]

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

Attached is an updated patch.

In addition to the code cleanup and bug fix suggestions, it includes a new base-case for factorial_partial_product.  Instead of:

if (n >= m)
    return n
if (n + 2 == m)
    return n*m
otherwise divide-and-conquer

It now does:

if (the_answer_will_fit_in_unsigned_long)
    compute_product_via_tight_loop()
    return answer
otherwise divide-and-conquer

It's around half the code of the previous factorial_partial_product(), if you don't count comments.  It's also much faster for small n and somewhat faster for moderate n.

original patch:
13: 0.848 usec
50: 2.4 usec
100: 4.68 usec
1000: 121 usec
10000: 7.68 msec
100000: 434 msec

new patch:
13: 0.5 usec
50: 1.2 usec
100: 2.28 usec
1000: 100 usec
10000: 7.32 msec
100000: 447 msec

I also experimented with adding Alexander's precompute logic to my factorial_loop.  However, it did not result in a significant speedup, since all of the cases that could leverage the precompute table now execute in the new fast base case.

The new patch includes the new unit tests I uploaded earlier.

----------
Added file: http://bugs.python.org/file17338/factorial.patch

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