Why is math.factorial much slower in Python 2.x than 3.x?
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 are1230 * computed separately, and then combined using a left shift.
See the Python Bugtracker issue for the discussion. Thanks DSM for pointing that out.