Message105715
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. |
|
Date |
User |
Action |
Args |
2010-05-14 14:58:06 | stutzbach | set | recipients:
+ stutzbach, rhettinger, mark.dickinson, belopolsky, draghuram |
2010-05-14 14:58:05 | stutzbach | set | messageid: <1273849085.86.0.611735138111.issue8692@psf.upfronthosting.co.za> |
2010-05-14 14:58:04 | stutzbach | link | issue8692 messages |
2010-05-14 14:58:04 | stutzbach | create | |
|