7

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.

4

2 回答 2

7

与@NPE 的回答相反，您的方法更快，仅适用于非常大的数字。对我来说，我开始看到分治法在输入 ~10^4 时变得更快。在 10^6 及以上，没有可比性，传统循环惨遭失败。

我不是硬件乘法器方面的专家，我希望有人可以对此进行扩展，但我的理解是乘法是逐位数进行的，就像我们在小学时所教的那样。

传统的阶乘循环将从小数字开始，结果不断增长。最后，您将一个巨大的数字与一个相对较小的数字相乘，由于数字不匹配，这是一个昂贵的计算。

前任。相比

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

第二个比较慢，因为结果增长很快，导致更快的计算成本更高。

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

于 2012-12-01T16:01:44.743 回答
3

简短的回答是你错了。它不是很快：

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差异更为显着。

于 2012-12-01T07:11:02.410 回答