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'); 
}