多线程大整数运算

Question

执行非常复杂的BigInteger操作非常慢，例如：

BigInteger.Pow(BigInteger(2),3231233282348);

我想知道是否有任何办法可以对这些基本数学函数进行多线程处理。

- Joe Thomas

---

答案将包含约1e12位数字；你真的想要那个答案吗？ - Dmitry Bychenko

哦不，那只是一个例子。我不会计算那么大的东西。我只想知道是否可以将这些操作多线程化。 - Joe Thomas

2^bigint n 等同于 1<<n，因此使用单个 for 循环或 memset（将零设置为 0）+ 一个 set（单个一位）应该非常容易和快速。如果您想加速操作，则可以加速操作 +、-、、/、<<、>>，这些操作是可并行化的（ 使用 Karatsuba 或使用 NTT）。请参见 https://dev59.com/Wuo6XIcBkEYKwwoYLhXh 和 https://dev59.com/i-o6XIcBkEYKwwoYLhXh。顺便说一句，即使 POW 也是可并行化的，如果您使用 x^y = exp2(y*log2(x))，则可以并行化乘法。 - Spektre

Answer 1

这取决于数学函数，但我真的看不出如何加快基本数学函数的速度。对于这些计算，进程中的下一步通常依赖于进程中的上一步。线程只有在您有部分可独立计算的计算时才会真正有所帮助。然后可以将它们组合在最后一步以产生结果。您需要自己将这些计算分解为可以并发运行的部分。

例如：

如果您有一个公式2 * 3 + 3 * 4。您可以运行两个线程，第一个计算2 * 3，第二个计算3 * 4。然后您可以在最后将结果汇总并将两个结果相加。您需要计算如何将计算拆分成更小的内容，然后相应地进行线程处理。

在您的幂例子中，您可以使用4个线程计算以下内容，然后通过乘以结果将其合并：

BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);

这样做并不能节省任何时间，因为所有 4 个核心都会试图计算同一个事情，最后你只是将它们相乘，这与单线程解决方案的效果相同。在某些处理器上，这甚至会更慢，因为它们通常会在其他核心空闲时加速其中一个核心。我使用与将 2^5 分解为 2^2 * 2^3 相同的方法来分解它。

- Graymatter

---

为了举例说明，我们以计算阶乘为例。一个线程可以计算1*2*3*4...，而另一个线程可以计算10*11*12。（是的，阶乘会很快生成大数，但这只是拆分的一个例子）最后，两个结果必须相乘。你也可以让每个线程在需要时获取下一个乘数，以便在它们之间良好地分配工作负载。如果无法拆分，就不幸了。 - ZoolWay

并行化乘法可以说是非常简单的（查找卡拉茨巴算法），对于其他操作我还没有深入思考，但我猜这样的笼统陈述也会在其他操作中出现错误（除法可能会有趣）。将幂函数拆分也很简单，考虑到基本数学公式a^(n+m) = a^n * a^m等。 - Voo

这根本不会节省你任何时间，因为所有4个核心都会围绕着尝试解决相同的事情而挣扎。这是数学问题，而不是存储操作，因此我不认为线程之间会有任何争用。真正的问题在于指数值导致的数字过大，无法实际使用。但从理论上讲，基本操作很容易并行化。 - Peter Duniho

Answer 2

的答案是

 BigInteger.Pow(BigInteger(2), 3231233282348);

将包含

  Log(2)/Log(10) * 3231233282348 == 9.727e11 

数字很多，因此需要900 GB来写下答案。这就是为什么它那么慢。

- Dmitry Bychenko

---

这只是一个例子。请参阅问题的评论。 - user395760

我不认为它回答了问题。问题不是为什么它很慢，而是如何使用多线程加速它。 - amit

Answer 3

如果您使用的是.NET 4.5版本，请了解异步等待(async await)：

http://blog.stephencleary.com/2012/02/async-and-await.html

- TamerM