有效计算乘积a * b ** 2 * c ** 3…

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乘法。

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