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?

What a weird task. Are there more specifics or did it just say "use threads"? — timgeb, Apr 07 '17 at 08:39
have you checked this https://wiki.python.org/moin/GlobalInterpreterLock ? — Surajano, Apr 07 '17 at 08:43
@timgeb **Here's the task itself, without changes:** Write a function that computes a large factorial using multiple threads — AlexNikolaev94, Apr 07 '17 at 08:49
@Surajano Maybe they simply want the students to practice synchronization. — ivan_pozdeev, Apr 07 '17 at 08:56
Your result will massively overflow before making any use of any threads. — The Quantum Physicist, Apr 07 '17 at 09:33

danbanica · Accepted Answer · 2017-04-07T09:24:11.363

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.

score 1 · Answer 2 · edited May 23 '17 at 12:10

I really like the idea presented in the other answer.

When the factorial is computed as the product of the numbers [1, n]:

numbers = range(1,n+1)

You can produce the numbers to be processed by the workers using slicing. For example:

slices = [numbers[i::nworkers] for i in range(nworkers)]
# using n = 10 and nworkers = 3, this produces:
# [[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]

Map this to a process pool, and then reduce the results of these products to get your final solution.

Don't use the threading module to implement this. This is a CPU bound task, that would be blocked by the Global Interpreter Lock. The multiprocessing module uses processes instead of threads to side-step this.

ivan_pozdeev · Answer 3 · 2017-04-07T10:47:48.227

A factorial is just a multiplication of a sequence of numbers. Since multiplication is associative, you can multiply the numbers in any order. More specifically, you can split the sequence into any number of parts any way you like, multiply the parts independently, then combine the results.

Due to CPython's GIL, you'll probably end up running a single thread at a time but the essence of the task is perhaps to simply practice thread synchronization.

threading.Thread and queue.Queue look like the right tools for the job. I'll give you two examples of possible implementations:

Create a single Queue and a number of Thread object, each of which would
- multiply a predefined range of numbers, then
- push the result into the queue.
start the threads and wait for them to finish
in the main thread, multiply all the numbers in the queue

Another, more interesting implementation is:

push all the numbers to multiply into a Queue
create a number of threads, each of which would
- start with an internal state of 1
- take a number from the Queue if it can (i.e. without blocking)
- multiply the state by it
The interesting part here is how to proceed after the queue is empty:
- threads can simply push the result into some other Queue and quit, leaving it up to the main thread do the final multiplication after all the threads quit
- instead, a thread may push the result back to the queue and quit. But then, you need to somehow make sure that not all threads quit before the final result is obtained (and pushed into the queue).
  - one way to do this is to keep track in an interlocked counter how many partial results have been pushed to the queue and prevent a thread from quitting if it detects it is to process the last one:
```
#at initialization
partial_results_lock = threading.Lock()
partial_results_left=<number of threads>

# in the thread, if the queue is empty
with partial_results_lock:
    queue.push(state)
    state=1
    partial_results_left-=1
    if partial_result_left!=0: return # after we start over and push
                                      #the final result, the counter will become -1
<start over>
```

Calculating factorial using multiple threads in Python

3 Answers3

Linked