¿Por qué math.factorial es mucho más lento en Python 2.x que en 3.x?

performance python-3.x

Question

Obtengo los siguientes resultados en mi máquina:

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

Pensé que esto podría tener algo que ver con la conversión int / long, pero factorial(10000L) no es más rápido en 2.7.

Answer 1

Python 2 usa el algoritmo factorial ingenuo :

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 usa el algoritmo factorial de dividir y conquistar :

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.

Vea el tema Python Bugtracker para la discusión. Gracias DSM por señalar eso.