[Python] Why is the "divide and conquer" method of computing factorials so fast for large ints?

I recently decided to look at factorial algorithms for large integers, and this "divide and conquer" algorithm is faster than a simple iterative approach and the prime-factoring approach:

def multiply_range(n, m):
print n, m
if n == m:
return n
if m < n:
return 1
else:
return multiply_range(n, (n+m)/2) * multiply_range((n+m)/2+1, m)

def factorial(n):
return multiply_range(1, n)


I understand why the algorithm works, it just breaks the multiplication into smaller parts recursively. What I don't understand is why this method is faster.

Continue reading...