是任何数字的阶乘是可并行的吗?

Question

任何数的阶乘计算都可以并行吗?如何?

Answer 1

当然可以，为什么不呢?乘法是结合法。a * (b * (c * d)) == ((a * b) * c) * d) == (a * b) * (c * d).分治并行化方案的含义应该是清楚的。

然而，这只会对许多数字的乘积有任何实际的好处，如果你谈论的是阶乘，这意味着你正在处理巨大的乘积，超出了任何计算机原生整数的范围，这意味着你正在处理任意精度的算术…在这种情况下，您可能有机会并行化单个乘法(Karatsuba乘法是递归的，基于FFT的乘法中的FFT也非常可并行化)，如果您可以用完所有的资源，那么在更高层并行化就没有意义了。

对于计算合理大小的阶乘，最快的方法可能是直接的单线程方法，它没有开销。