有效地计算产品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.

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