java - 有效地计算乘积 a * b² * c³ ...

Question

计算乘积的最有效方法是什么

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

假设平方的成本大约是乘法的一半？操作数少于100个。

对于乘法时间与操作数长度的平方成正比的情况(如java.math.BigInteger)，是否也有一个简单的算法？

---

第一个(也是唯一一个)答案是完美的 w.r.t.操作次数。

有趣的是，当应用于可观的 BigInteger 时，这部分根本无关紧要。即使在没有任何优化的情况下计算 abbcccddddeeeee 也需要大约相同的时间。

大部分时间花在最后的乘法上(BigInteger 没有实现任何更智能的算法，如 Karatsuba、Toom–Cook 或 FFT，所以时间是二次方的)。重要的是确保中间被乘数的大小大致相同，即给定大小大致相同的数字 p, q, r, s，计算 (pq) (rs) 通常比 ((pq) r) s 快。对于几十个操作数，速度比似乎约为 1:2。

更新

在 Java 8 中，BigInteger 中同时存在 Karatsuba 和 Toom–Cook 乘法。

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 输入参数。