高效计算a * b² * c³ ... 的乘积

Question

如何以最高效的方式计算乘积？

a¹ b² c³ d⁴ e⁵ ...

假设平方运算的成本约为乘法成本的一半，操作数少于100个。

如果乘法时间与操作数长度的平方成正比（例如java.math.BigInteger），是否也有简单的算法呢？

---

第一个（也是唯一的）答案在操作次数方面非常完美。

有趣的是，当应用于相当大的BigInteger时，这一部分根本无关紧要。甚至没有任何优化的计算abbcccddddeeeee大约需要相同的时间。

大部分时间都花费在最后的乘法上（BigInteger没有实现类似Karatsuba、Toom-Cook或FFT这样的更智能的算法，因此时间复杂度为二次）。重要的是确保中间乘积的大小大致相同，即给定大约相同大小的数字p、q、r、s，计算(pq)(rs)通常比计算((pq)r)s更快。对于数十个操作数，速度比大约为1:2。

更新

在Java 8中，BigInteger中有Karatsuba和Toom-Cook乘法。

- maaartinus

---

看起来是一个合理的面试问题... 基本解决方案（不是最优解）是单独计算每个成员的幂（乘法的log2（Power）），然后将结果相乘... - Alexei Levenkov

有一种O(N log(N)^2)的算法可以实现这个功能（其中N是最终数字的大小）。但是你需要超越java.math.BigInteger才能实现它。 - Mysticial

操作数的类型是什么？int吗？ - Adam Stelmaszczyk

@Adam：实际上，这些操作数是“BigInteger”，但目前我不知道有多大。 - maaartinus

BigInteger没有实现像Karatsuba、Toom-Cook或FFT这样的更智能的算法，因此时间是二次的。这适用于哪个java.math.BigInteger的实现？ - greybeard

@灰须 更新了...在一些古老的时代里（我不知道历史），它并不存在。 - maaartinus

Answer 1

我完全不确定这是否是最优解(尽管我认为渐进优化是最优的)，但您可以通过 O(N) 次乘法实现。您可以按以下方式分组 a * b^2 * c^3 的参数: c * (c*b) * (c*b*a)。伪代码如下:

result = 1
accum = 1
for i in 0 .. arguments:
  accum = accum * arg[n-i]
  result = result * accum

我认为它是渐进最优的，因为你必须使用 N-1 个乘法来乘以 N 个输入参数。

- jpalecek

---

看起来这个程序的时间复杂度大约是O(N^2)。对于OP来说似乎足够好了，所以给一个加1。但是，从渐进意义上讲，它并不是最优的，因为可以使用非常难以实现的算法在O(N log(N)^2)的时间内完成。 - Mysticial

有了他目前的伪代码，它可以在O(n)时间内运行。他的代码缓存先前的乘法，因此只进行2*n次乘法。所有这些都是针对输入参数数量n的。 - Sebastian Graf

BigInteger 上的乘法不是常量时间。 - Mysticial

啊，那就说得通了。我没意识到那是个限制。 - Sebastian Graf

@Mysticial：当然，你在乘法时间方面是正确的，但它有点偏离我的问题。这个解决方案以线性乘法次数运行，另一个问题是每个乘法需要二次时间。你不能说时间是O(n ** 2)（使用BigInteger或更好的一些疯狂算法），因为有两个输入：数字的大小和项数。 - maaartinus

Answer 2

如2012年10月26日编辑中提到的：
由于乘法时间与操作数的大小呈超线性关系，因此保持长时间操作的操作数大小相似将具有优势（特别是如果唯一可用的Toom-Cook是toom-2（Karatsuba））。 如果不进行完全优化，则将操作数放入队列中，以允许按递增（显着）长度的顺序弹出它们似乎是一个不错的尝试。
然而，还有特殊情况：0、2的幂、其中一个因子是“琐碎”的乘法（“长乘单位数乘法”，线性地求和因子长度）。
而且，平方比一般乘法更简单/更快（问题建议假设½），这将建议以下策略：

• 在预处理步骤中，按指数加权计算尾随零的数量
  遇到0时结果为0
• 去除尾随零，丢弃结果为1的值
  如果没有剩余值，则结果为1
• 查找并合并出现多次的值
• 设置一个队列，允许提取“最短”的数字。对于每一对（数字，指数），插入exponentiation by squaring将乘以的因子
• 可选：组合“平凡因子”（见上文）并重新插入
  不确定如何进行。假设长度为12的因子是平凡的，并且初始因子的长度为1、2、…、10、11、12、…、n。最优情况下，您将1+10、2+9等组合起来，共得到12个因子中的7个平凡因子。选择最短的组合得到3、6、9、12，共得到12个因子中的8个因子。
• 提取最短的一对因子，相乘并重新插入
  一旦只剩下一个数字，结果就是第一步中附加了零的数字

（如果因数分解很便宜，那么为了从便宜的平方中获得最大收益，它必须尽早进行。）

- greybeard