c# - BigInteger阶乘的并行计算

Question

作为我的 BigDecimal 库的一部分，我需要计算任何给定非负整数的阶乘。所以我使用 .Net 4.0 的 System.Numerics.BigInteger 来存储大量数据。这是我正在使用的功能:

private BigInteger Factorial(BigInteger x)
{
     BigInteger res = x;
     x--;
     while (x > 1)
     {
          res *= x;
          x--;
     }
     return res;
}

它正在运行但未优化。现在我想使用并行计算，所以这是我尝试过的:(我没有并行编程的经验)

public BigInteger Factorial(long x)
{
     BigInteger res = 1;
     ParallelLoopResult r = Parallel.For(2L, (x + 1), i =>
          res *= i
     );
     return res;
}

奇怪的问题是，上面的函数对于像 5 这样的小数字非常有效!但不适用于 1000 这样的大数字!并且每次都返回完全不同的结果。所以我意识到它不是线程安全的，问题出在变量 res 上。我想知道正确的实现是什么？
如果我可以使用 BigInteger 而不是 long 变量 x 会更好。

Answer 1

您需要确保您的并行进程不共享任何状态。

例如，在阶乘的情况下，我会执行以下操作:

• 设置并行度 (DOP) - 通常是计算机上用于计算密集型操作的处理器数量
• 将问题分成独立的子集
• 并行处理每个子集
• 汇总从并行过程中获得的结果

这在某种程度上是一个简化的 Map-Reduce 。

问题在于将一组数字相乘。将此集合划分为子集的一种方法是使用 N 并行 for 循环，其中每个循环都从值 i(其中 0 < i <= N)开始，步长为 N(和 N = DOP)。

这是执行此操作的代码:

/// <summary>
/// The max number of parallel tasks
/// </summary>
static readonly int DegreeOfParallelism = Environment.ProcessorCount;

public BigInteger Factorial(long x)
{
    // Make as many parallel tasks as our DOP
    // And make them operate on separate subsets of data
    var parallelTasks =
        Enumerable.Range(1, DegreeOfParallelism)
                    .Select(i => Task.Factory.StartNew(() => Multiply(x, i),
                                 TaskCreationOptions.LongRunning))
                    .ToArray();

    // after all tasks are done...
    Task.WaitAll(parallelTasks);

    // ... take the partial results and multiply them together
    BigInteger finalResult = 1;

    foreach (var partialResult in parallelTasks.Select(t => t.Result))
    {
        finalResult *= partialResult;
    }

    return finalResult;
}

/// <summary>
/// Multiplies all the integers up to upperBound, with a step equal to DOP
/// starting from a different int
/// </summary>
/// <param name="upperBoud"></param>
/// <param name="startFrom"></param>
/// <returns></returns>
public BigInteger Multiply(long upperBound, int startFrom)
{
    BigInteger result = 1;

    for (var i = startFrom; i <= upperBound; i += DegreeOfParallelism)
        result *= i;

    return result;
}

在我的机器上，这会在大约 30 秒内计算出 100000!，结果是 what Wolfram Alpha says it should be。

更新

再运行几次测试后，我发现了一些出乎我意料的事情:将 100000! 结果打印到控制台需要大约 18 秒(结果有 456574 数字)。

100000! 单独计算(不打印数字)的结果是:

• ~10 秒并行执行
• ~16 秒顺序执行