Author stutzbach
Recipients mark.dickinson, rhettinger, stutzbach
Date 2010-05-11.20:22:56
SpamBayes Score 0.000426427
Marked as misclassified No
Message-id <1273609381.14.0.711112369478.issue8692@psf.upfronthosting.co.za>
In-reply-to
Content
(Making an educated guess about who to add to the Nosy list)

Attached is a patch to improve math.factorial by using a divide-and-conquer algorithm.  The old algorithm performs n-1 multiplications, mostly on numbers with a very large number of digits.

The algorithm in this patch:
- implicitly factors out all powers of two and applies a left-shift at the end.
- performs roughly half as many multiplications (around n/2 + 2*lg n)
- groups the multiplications so most multiplications are on small numbers
- uses a lookup table for n <= 12

There are faster factorial algorithms available, but they're significantly more complicated and rely on a fast prime factorization function.  This one is around 125 lines of code in C (with comments).  I have a pure-Python version that's around 25 lines of code, if anyone is interested.

Here are some timing results for different values of n:

n : old algorithm : new algorithm
1       0.14 us      0.10 us
10      0.63 us      0.12 us
13      0.81 us      0.76 us
100    12.6  us      4.92 us
1k    576    us    118    us
10k    53.6  ms      8.16 ms
100k   12.1  s     443    ms
1M      27   min    23    s
10M    forget it    20    min

I tested that both algorithms return the same answer for all values of n up to 10,000.
History
Date User Action Args
2010-05-11 20:23:01stutzbachsetrecipients: + stutzbach, rhettinger, mark.dickinson
2010-05-11 20:23:01stutzbachsetmessageid: <1273609381.14.0.711112369478.issue8692@psf.upfronthosting.co.za>
2010-05-11 20:22:58stutzbachlinkissue8692 messages
2010-05-11 20:22:58stutzbachcreate