Dlaczego współczynnik math.factorial jest znacznie wolniejszy w Pythonie 2.x niż 3.x?

Question

uzyskać następujące wyniki na moim komputerze:

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

myślałem, że to może mieć coś wspólnego z int/long nawrócenia, ale factorial(10000L) nie jest szybciej w 2,7.

Answer 1

Pythona 2 wykorzystuje 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 } 

Pythona 3 wykorzystuje 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. 

Patrz Python Bugtracker issue do dyskusji. Dzięki DSM za wskazanie tego.