为什么“分而治之"?大整数的阶乘计算方法如此之快? [英] 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.

推荐答案

与@NPE的答案相反，您的方法更快，仅适用于非常大的数字. 对我来说，我开始看到对于输入〜10 ^ 4，分而治之方法变得更快.在10 ^ 6及更高级别，没有任何可比性，传统循环会惨败.

Contrary to @NPE's answer, your method is faster, only for very large numbers. For me, I began to see the divide and conquer method become faster for inputs ~10^4. At 10^6 and above there is no comparison a traditional loop fails miserably.

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

I'm no expert on hardware multipliers and I hope someone can expand on this, but my understanding is that multiplication is done digit for digit same way we are taught in grade school.

传统的阶乘循环将从小数开始，结果不断增长.最后，您要用一个相对较小的数字来混淆一个巨大的数字，由于数字不匹配，所以计算起来很昂贵.

A traditional factorial loop will start with small numbers and the result keeps growing. In the end you are muliplying a ginormous number with a comparatively small number, an expensive calculation due to the mismatch in digits.

例如比较

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

第二个比较慢，因为结果增长很快，导致更快地进行更昂贵的计算.

the second is slower because the result grows fast, leading to more expensive calculations sooner.

对于大数，您的方法比这两个方法都快几个数量级，因为它会将阶乘分解为相似大小的部分.子结果的位数相似，并且乘法速度更快.

Your method is faster than either of these by orders of magnitude for large numbers because it divides the factorial into similarly sized parts. The sub-results have similar numbers of digits and multiply faster.

这篇关于为什么“分而治之"?大整数的阶乘计算方法如此之快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！