[New-bugs-announce] [issue8692] Use divide-and-conquer for faster factorials

[Daniel Stutzbach]

New submission from Daniel Stutzbach <daniel at 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 <report at bugs.python.org>
<http://bugs.python.org/issue8692>
_______________________________________