Why is the “divide and conquer” method of computin

Question

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.

Answer 1

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.

ex. compare

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.

Answer 2

The short answer is that you're mistaken. It is not very fast:

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

In other words, it is about three times slower than a straightforward one-liner.

For smaller values of n the difference is even more dramatic.