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

Question

puedo obtener 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 long int /, pero factorial(10000L) no es más rápido en 2.7.

Answer 1

Python 2 utiliza el 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 utiliza la 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. 

Véase el Python Bugtracker issue para la discusión. Gracias DSM por señalar eso.