Parallelizing Factorial Calculation

Question

I want to write a program that computes the factorial of an integer, using parallel computation (Open MP library).

Clearly the program below suffers from race condition.

// Each loop iteration writes a value that a different iteration reads.
#pragma omp parallel for
for (i=2; i < 10; i++)
{
   factorial[i] = i * factorial[i-1];
}

I read somewhere that pow and factorial calculations can in no way done in parallel. So, is this true, or can the above program (in C, using OPenMP library) be modified to calculate factorial in parallel?

Answer 1

You can do this in parallel by running over the array twice. The first time you calculate the partial products and save the total partial product per thread. In the second pass you correct each element by the total product from the previous thread. This is similar to how to do a cumulative sum (aka prefix sum) in parallel except it's the cumulative product in parallel.

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(void) {
    int n = 10;
    int factorial[n];
    factorial[1] = 1;

    int *proda;
    #pragma omp parallel
    {
        int ithread = omp_get_thread_num();
        int nthreads = omp_get_num_threads();
        #pragma omp single
        {
            proda = malloc(nthreads * sizeof *proda);
            proda[0] = 1;
        }
        int prod = 1;
        #pragma omp for schedule(static) nowait
        for (int i=2; i<n; i++) {
            prod *= i;
            factorial[i] = prod;
        }
        proda[ithread+1] = prod;
        #pragma omp barrier
        int offset = 1;
        for(int i=0; i<(ithread+1); i++) offset *= proda[i];
        #pragma omp for schedule(static)
        for(int i=1; i<n; i++) factorial[i] *= offset;
    }
    free(proda);

    for(int i=1; i<n; i++) printf("%d\n", factorial[i]); putchar('\n'); 
}

Answer 2

If it is a big number, you can do a parallel factorial if you split your multiplications

Example

Number is 1000! and you have 10 threads

1. Thread resolve 2*3*4*5*.....*100 and save it in t1

2. Thread resolve 101*102*103 .... *200 and save it in t2

   ....

10) Thread resolve 900*901*902*....*1000 and save it in t10

Then on the main thread you resolve:

t1*t2*t3*...*t10 and it is equal to 1000!