Calculating factorial using multiple threads in Python

Question

I use Python 2.7 and I have a task to write a function that calculates factorial using multiple threads. I tried to do that using traditional recursive approach, like

def factorial(n):
    if n < 1:
        return 1
    else:
        return n * factorial(n - 1)

But it seems that this way doesn't suite for multithreading. Are there any ways to calculate factorial using multiple threads?

Answer 1

In multi-threading applications it is best to minimize the data dependencies that exists between the different threads.

In the recursive solution for factorials that you have mentioned it is hard to find calculations that do not depend on the results of other calculations.

A distinct approach would be to split the factorial in multiple parts. For example, for two threads one could do something like this:

n! = [1 * 2 * 3 * .. * (n/2)] * [(n/2 + 1) * ... * n]

The first thread would calculate the value:

v1 = 1 * 2 * 3 * .. * (n/2)

The second thread would calculate:

v2 = (n/2 + 1) * ... * n

And afterwards, when both threads are finished, the main thread would compute n! = v1 * v2.

This can be generalized to use k threads by splitting the input factorial into k different parts instead of just two, as in the above example.