最近，我决定看看在大的整数阶乘的算法，而这种“分而治之”的算法是不是一个简单的迭代方法和总理保理方法快：
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)
我明白为什么算法的工作，它只是打破了乘法成较小的部分递归。 我不明白的是为什么这种方法更快。
相反，@ NPE的答案，你的方法是更快，只为非常大的数字。 对于我来说，我开始看到了分而治之的方法成为输入〜10 ^ 4更快。 在10 ^ 6和以上没有比较传统的循环悲惨地失败。
我对硬件乘法器不是专家，我希望有人可以在此展开，但我的理解是，乘法，因为我们被教导在小学位数相同的方式完成的数字。
传统的阶乘环路将开始与小的数字，结果不断增加。 到底你muliplying具有相对小的数目，一个昂贵的计算一个极大的相数，由于在数字的失配。
恩。 相比
reduce(operator.mul, range(1,10**5))
reduce(operator.mul, range(10**5,1,-1))
第二个比较慢，因为结果长得快，导致更昂贵的计算越快。
你的方法是通过对大量的数量级比任何这些快，因为它分割成阶乘同样大小的部分。 子结果有位相似数量和繁殖更快。
简短的回答是，你错了。 它是不是非常快：
In [34]: %timeit factorial(100)
10000 loops, best of 3: 57.6 us per loop
In [35]: %timeit reduce(operator.mul, range(1, 101))
100000 loops, best of 3: 19.9 us per loop
换句话说，它比一个简单的一行慢大约三倍。
对于较小的值n的差异更为显着。
