并行计算阶乘

Question

我想编写一个程序，使用并行计算（Open MP库）来计算一个整数的阶乘。

显然，下面的程序存在竞争条件。

// 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];
}

我在某个地方读到，pow和阶乘计算无论如何都不能并行处理。那么，这是真的吗？或者上面的程序（使用OPenMP库，在C语言中）可以被修改为并行计算阶乘？

- ferrer

---

顺便问一下，为什么你需要一个阶乘数组？阶乘的大小增长非常迅速。你可能应该以某种方式对值进行归一化，以保持其有界。另请参见斯特林公式近似。 - Z boson

Answer 1

您可以通过两次运行数组来并行执行此操作。第一次计算部分乘积并保存每个线程的总部分乘积。在第二遍中，您通过前一个线程的总乘积更正每个元素。这类似于如何在并行中执行累加求和（又称为前缀和），只不过是在并行中执行累积乘积。

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

- Z boson

Answer 2

如果这是一个大数，您可以通过分割乘法来进行并行阶乘。

示例：

数字为1000！，您有10个线程

1. 线程计算2 * 3 * 4 * 5 * ..... * 100，并将其保存在t1中 2. 线程计算101 * 102 * 103 .... * 200，并将其保存在t2中 3. ... 10. 线程计算900 * 901 * 902 * .... * 1000，并将其保存在t10中

然后在主线程上计算：

t1 * t2 * t3 * ... * t10，它等于1000！

- ganchito55