Daniel Stutzbach <[email protected]> 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 <[email protected]>
<http://bugs.python.org/issue8692>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
