大整数阶乘的并行计算

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代替变量x，那就更好了。

- SepehrM

Answer 1

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

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

• 设置并行度（DOP）-通常是计算限制操作机器上的处理器数量
• 将问题分成独立的子集
• 并行处理每个子集
• 聚合从并行进程获得的结果

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

问题在于将一组数字相乘。将此集合分成子集的一种方法是使用N个并行循环，其中每个循环从值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;
}

在我的电脑上，计算100000!大约需要30秒钟，并且结果与Wolfram Alpha给出的结果相同。

更新：

在运行了更多测试后，我发现了一些意外的事情：将100000!结果打印到控制台需要约18秒钟（结果有456574位数）。

仅对100000!进行计算（不打印数字）的结果如下：

• 并行执行约10秒钟
• 顺序执行约16秒钟

- Cristian Lupascu

---

巧妙的技巧：_i += DegreeOfParallelism_。您可以使用Environment.ProcessorCount作为DegreeOfParallelism。 - Jeroen van Langen

@SepehrM，最后一个for循环中出现了一个偏移量错误（应该是i <= upperBound而不是i < upperBound）。我已经修复了它。 - Cristian Lupascu

谢谢，它运行得很好。DOP 应该是 CPU 核心数还是线程数？ - SepehrM

我使用实际的CPU核心数量作为DOP时，可以获得更好的结果。 - SepehrM

@SepehrM 在这种情况下，CPU 是瓶颈，拥有更高的 DOP 可以实现实际处理和线程之间的上下文切换。 - Cristian Lupascu

Answer 2

前言

经过一些最初的简单基准测试，对于真正大的阶乘（大于 ~1000!），并行版本的速度更快。对于较小的阶乘， 并行处理的开销超过了其他所有因素，顺序版本仅仅更快。

代码

话虽如此，以下是我在 LINQPad 中得到的结果：

public static class Math
{
    // Sequential execution
    public static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger x)
    {
        System.Numerics.BigInteger res = x;
        x--;
        while (x > 1)
        {
            res *= x;
            x--;
        }
        return res;
    }
    
    public static System.Numerics.BigInteger FactorialPar(System.Numerics.BigInteger x)
    {
        return NextBigInt().TakeWhile(i => i <= x).AsParallel().Aggregate((acc, item) => acc * item);
    }
    
    public static IEnumerable<System.Numerics.BigInteger> NextBigInt()
    {
        System.Numerics.BigInteger x = 0;
        while(true)
        {
            yield return (++x);
        }
    }
}

这适用于小的（5！= 120，6！= 720）和大的（~8000！）阶乘。但是，正如我之前提到的那样，对于小的阶乘来说会有严重的性能惩罚（高达两个数量级），但对于大的阶乘则可以加快速度（2-3倍）。以下是在LINQPad预热后的结果：

• 6! x 20 -> 串行平均ticks /标准偏差：4.2 / 2.014，并行平均ticks /标准偏差：102.6 / 39.599（并行执行慢25倍...）

• 300! x 20 -> 串行平均ticks /标准偏差：104.35，并行平均ticks /标准偏差：405.55 / 175.44（并行运行速度是顺序的1/4）

• 1000! x 20-> 串行平均ticks /标准偏差：2672.05 / 615.744，并行平均ticks /标准偏差：3778.65 / 3197.308（并行运行速度约为顺序速度的70-90％）

• 10000! x 20 -> 串行平均ticks /标准偏差：286774.95 / 13666.607，并行平均ticks /标准偏差：144932.25 / 16671.931（并行速度快2倍）

要注意这些结果需要编译成发布版本并作为独立版本运行才能得到真实的结果，但有一个值得考虑的趋势。在我使用LINQPad进行并行执行时，100000！（包括打印等操作）花费了26秒。

- Patryk Ćwiek

---

这似乎是一种更快的方法，但在我的测试中，我没有看到任何性能差异，因为计算并将1,000,000！存储在变量中的两个答案都需要6.5分钟。 - SepehrM

Answer 3

尝试以下更简单的解决方案：

Func<int, BigInteger> factorialAgg = n => n < 2 ? BigInteger.One 
                      : Enumerable.Range(2, n-1)
                        .AsParallel()
                        .Aggregate(BigInteger.One, (r, i) => r * i);

var result = factorialAgg(100000);

- GKA

---

而对于更短的一个：Func<int, BigInteger> Factorial = n => Enumerable.Range(1, n).AsParallel().Aggregate(BigInteger.One, (r, i) => r * i); - Kobor42

@Kobor42，你更新我的答案的版本多了一个不必要的乘1操作...它还会生成0、1的范围。我认为这样并不高效。我最初确实是这样做的，但无论你在哪里查看阶乘的实现，都会检查0、1并立即返回，而你则对大于1的范围进行其余的计算...这是有原因的... - GKA

@GKA 你说得对。我没有关注到那一部分。我更在意额外的类型转换和添加并行性的可能性。正确实现的并行聚合确实可以大大提高速度。可惜，在4.5.1上并不会。我已经测试过了。 :-( 无论如何，我采纳了你的建议。 - Kobor42

@GKA 你使用的Aggregate重载不会并行工作，因为不知道如何组合累积结果。你应该使用没有seed的重载：ParallelEnumerable.Range(2, n-1).Select(i => (BigInteger)i).Aggregate((a, b) => a*b)。或者使用指定如何组合累积值的重载：ParallelEnumerable.Range(2, n-1).Aggregate(BigInteger.One, (a, b) => a*b, (c, d) => c*d, e => e)。 - user4003407

@Kobor42，您编辑了这个问题，但由于代码减少，您更改了“Aggregate”重载，这导致它不适合并行调用。 - user4003407

@PetSerAl 很不幸，我现在看到的不是我的原始答案，而是 Kobor42 编辑过的答案。我的原始答案使用了正确的函数。 - GKA