BigInteger阶乘的并行计算 [英] Parallel calculation of BigInteger factorial

问题描述

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

As a part of my BigDecimal library, I need to calculate the factorial of any given non negative integer. So I'm using .Net 4.0 's System.Numerics.BigInteger to be able to store huge numbers. Here is the function I'm using:

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

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

It's working but not optimized. Now I want to use parallel computing, so here is what I've tried: (I have no experience with parallel programming)

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，那会更好.

The weird problem is that the above function works perfectly for small numbers like 5! but doesn't work for big numbers like 1000! and each time returns a completely different result. So I realized it's not thread safe and the problem is with the variable res. I wonder what the correct implementation is?
And It would be nicer if I could use BigInteger instead of long for variable x.

推荐答案

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

You need to make sure your parallel processes do not share any state.

例如，对于阶乘，我将执行以下操作:

For example, in the case of the factorial, I would do the following:

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

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

This is somehow a simplified Map-Reduce.

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

The problem consists in multiplying together a set numbers. One way to divide this set into subsets is to use N parallel for loops where each start at a value i (where 0 < i <= N) with a step of N (and N = DOP).

这是执行此操作的代码:

Here's the code that does that:

/// <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!，结果为 Wolfram Alpha应该说的是什么.

On my machine this computes 100000! in about 30 seconds and the result is what Wolfram Alpha says it should be.

再运行几次测试后，我发现了意料之外的事情:将100000!结果打印到控制台需要大约18秒(结果为456574位).

After running a few more tests, I discovered something which I didn't expect: printing out the 100000! result to the console takes ~18 seconds (the result has 456574 digits).

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

The results of the 100000! computation alone (without printing the number) the are:

• 〜10秒用于并行执行
• 〜16秒用于顺序执行

这篇关于BigInteger阶乘的并行计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！