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

math java biginteger arbitrary-precision

2022-09-04 22:24:34

计算产品的最有效方法是什么

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

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

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

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

有趣的是，当应用于相当大的s时，这部分根本不重要。即使计算abcccddddeee没有任何优化也需要大约相同的时间。BigInteger

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

更新

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

答案 1

我绝对不知道这是否是最优方法（尽管我认为它是渐近最优的），但你可以通过乘法来完成这一切。您可以对参数进行分组，如下所示：.在伪代码中：O(N)a * b^2 * c^3c * (c*b) * (c*b*a)

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

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

答案 2

正如10月26'12编辑中提到的：
由于乘法时间在操作数的大小上是超线性的，因此保持长操作的操作数大小相似将是有利的（特别是如果唯一可用的Toom-Cook是toom-2（Karatsuba））。如果不进行完全优化，将操作数放入队列中，允许按增加（显着）长度的顺序弹出它们，从臀部看是一个不错的镜头。
然后，还有特殊情况：0，2的幂，乘法，其中一个因子是（否则）“平凡”的（“长乘以个位数乘法”，因子长度之和的线性）。
平方比一般乘法更简单/更快（问题建议假设1/2），这将建议以下策略：

在预处理步骤中，如果遇到 0，则按指数
结果 0 加权的尾随零进行计数
删除尾随零，如果没有剩余值，则丢弃结果值 1
结果 1
查找并合并多次出现的值
设置一个允许提取“最短”数字的队列。对于每对（数字，指数），插入乘以平方的因子幂
可选：结合“琐碎因素”（见上文）并重新插入
不确定如何执行此操作。假设长度为 12 的因子，其中平凡，初始因子的长度为 1，2，...，10，11，12，...，n。理想情况下，您可以组合1 + 10，2 + 9，...对于 12 个平凡的 7 个因素。将最短的结合得到3，6，9，12从12到8
提取最短的因子对，乘法并在只有一个数字后重新插入
，结果是第一步的零被附加到

（如果因式分解很便宜，那么它必须很早就进行，才能从廉价的平方中获得最大收益。