Author stutzbach
Recipients belopolsky, draghuram, mark.dickinson, rhettinger, stutzbach
Date 2010-05-14.14:58:02
SpamBayes Score 9.00101e-06
Marked as misclassified No
Message-id <1273849085.86.0.611735138111.issue8692@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2010-05-14 14:58:06stutzbachsetrecipients: + stutzbach, rhettinger, mark.dickinson, belopolsky, draghuram
2010-05-14 14:58:05stutzbachsetmessageid: <1273849085.86.0.611735138111.issue8692@psf.upfronthosting.co.za>
2010-05-14 14:58:04stutzbachlinkissue8692 messages
2010-05-14 14:58:04stutzbachcreate