为什么Python 2.x中的math.factorial比3.x慢得多？

Question

我在计算机上得到以下结果：

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
>>>

我认为这可能与int / long转换有关，但factorial(10000L)在2.7中并没有更快的速度。

Answer 1

Python
2使用朴素的阶乘算法：

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使用分治法阶乘算法：

1229 * factorial（n）的形式为2 ** k * m，m为奇数。k和m是
1230 *单独计算，然后使用左移组合。

有关讨论，请参见Python Bugtracker问题。感谢DSM指出这一点。