Why is math.factorial much slower in Python 2.x than 3.x?

Question

I get the following results on my machine:

Python 3.2.2 (default, Sep  4 2011, 09:51:08) [MSC v.1500 32 bit (Intel)] on win 32 Type "help", "copyright", "credits" or "license" for more information. >>> import timeit >>> timeit.timeit('factorial(10000)', 'from math import factorial', number=100) 1.9785256226699202 >>>  Python 2.7.2 (default, Jun 12 2011, 15:08:59) [MSC v.1500 32 bit (Intel)] on win 32 Type "help", "copyright", "credits" or "license" for more information. >>> import timeit >>> timeit.timeit('factorial(10000)', 'from math import factorial', number=100) 9.403801111593792 >>> 

I thought this might have something to do with int/long conversion, but factorial(10000L) isn't any faster in 2.7.

Answer 1

Python 2 uses the naive factorial algorithm:

1121 for (i=1 ; i<=x ; i++) { 1122     iobj = (PyObject *)PyInt_FromLong(i); 1123     if (iobj == NULL) 1124         goto error; 1125     newresult = PyNumber_Multiply(result, iobj); 1126     Py_DECREF(iobj); 1127     if (newresult == NULL) 1128         goto error; 1129     Py_DECREF(result); 1130     result = newresult; 1131 } 

Python 3 uses the divide-and-conquer factorial algorithm:

 1229 * factorial(n) is written in the form 2**k * m, with m odd. k and m are 1230 * computed separately, and then combined using a left shift. 

See the Python Bugtracker issue for the discussion. Thanks DSM for pointing that out.