为什么对于大的整数,计算阶乘的"分而治之"方法如此之快？

Question

我最近决定研究大整数的因子算法,这种"分而治之"的算法比简单的迭代方法和素因子方法更快:

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)

我理解为什么算法有效,它只是递归地将乘法分成更小的部分.我不明白的是为什么这种方法更快.

Answer 1

相反,@ NPE的答案,你的方法是更快,只为非常大的数字.对我来说,我开始看到分输和征服方法变得更快输入~10 ^ 4.在10 ^ 6及以上,没有比较传统的循环失败.

我不是硬件乘法器方面的专家,我希望有人可以对此进行扩展,但我的理解是乘法在数字上完成数字,就像我们在小学里教的那样.

传统的阶乘循环将以较小的数字开始,结果不断增长.最后,你正在用一个相对较小的数字来代表一个巨大的数字,由于数字的不匹配,这是一个昂贵的计算.

恩.相比

reduce(operator.mul, range(1,10**5))
reduce(operator.mul, range(10**5,1,-1))

第二个是较慢的,因为结果快速增长,导致更快的计算更昂贵.

对于大数字,您的方法比其中任何一个都快几个数量级,因为它将阶乘分成类似大小的部分.子结果具有相似的数字位数并且乘以更快.