<分区>
我最近决定研究大整数的阶乘算法，这种“分而治之”算法比简单的迭代方法和质因数分解方法更快:
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 及以上时，没有可比性，传统循环会惨败。
我不是硬件乘法器方面的专家，我希望有人可以对此进行扩展，但我的理解是乘法是一个数字一个数字地完成的，就像我们在小学所教的那样。
传统的阶乘循环将从小数开始，结果不断增长。最后，您将一个巨大的数字与一个相对较小的数字相乘，由于数字不匹配，计算成本很高。
例如。比较
reduce(operator.mul, range(1,10**5))
reduce(operator.mul, range(10**5,1,-1))
第二个较慢，因为结果增长很快，导致更快地进行更昂贵的计算。
对于大数，您的方法比这两种方法都快几个数量级，因为它将阶乘分成大小相似的部分。子结果具有相似的位数并且乘法更快。
关于python - 为什么 "divide and conquer"计算阶乘的方法对于大整数这么快？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13657265/