Message105537
(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. |
|
Date |
User |
Action |
Args |
2010-05-11 20:23:01 | stutzbach | set | recipients:
+ stutzbach, rhettinger, mark.dickinson |
2010-05-11 20:23:01 | stutzbach | set | messageid: <1273609381.14.0.711112369478.issue8692@psf.upfronthosting.co.za> |
2010-05-11 20:22:58 | stutzbach | link | issue8692 messages |
2010-05-11 20:22:58 | stutzbach | create | |
|