New submission from Daniel Stutzbach <dan...@stutzbachenterprises.com>:
(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. ---------- assignee: stutzbach components: Extension Modules files: factorial.patch keywords: needs review, patch, patch messages: 105537 nosy: mark.dickinson, rhettinger, stutzbach priority: normal severity: normal stage: patch review status: open title: Use divide-and-conquer for faster factorials type: performance versions: Python 3.2 Added file: http://bugs.python.org/file17300/factorial.patch _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue8692> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
