13

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

a 1 b 2 c 3 d 4 e 5 ...

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

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

第一个（也是唯一的）答案是完美的操作数量。

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

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

更新

在 Java 8 中，在BigInteger.

4

2 回答 2

8

我绝对不知道这是否是最佳方法（尽管我认为它是渐近最佳的），但是您可以通过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输入参数。

于 2012-10-25T22:01:38.200 回答
1

如2012 年 10 月 26 日编辑中所述：
由于操作数大小的乘法时间超线性，保持操作数大小以进行类似的长操作将是有利的（特别是如果唯一可用的 Tom-Cook 是 tom-2 （唐叶））。如果不进行全面优化，将操作数放入队列中，允许按增加（显着）长度的顺序弹出它们，看起来不错。
再说一次，有一些特殊情况：0，2 的幂，乘法，其中一个因子（否则）是“微不足道的”（“long-by-single-digit multiplication”，与因子长度之和成线性关系）。
并且平方比一般乘法更简单/更快（问题建议假设 ½），这将建议以下策略：

  • 在预处理步骤中，
    如果遇到 0，则计算由指数结果 0 加权的尾随零
  • 删除尾随零，
    如果没有剩余值，则丢弃 1 结果 1 的结果值
  • 查找并组合多次出现的值
  • 设置允许提取“最短”号码的队列。对于每一对（数字，指数），插入乘方乘幂的因子
  • 可选：结合“微不足道的因素”（见上文）并重新插入
    不知道如何去做。假设长度为 12 的因子是微不足道的，初始因子的长度为 1、2、…、10、11、12、…、n。最佳情况下，您将 1+10、2+9、... 组合为 12 中的 7 个微不足道的因素。组合最短为 3、6、9、12 为 12 中的 8
  • 提取最短的因子对，相乘并在只有一个数字时重新插入
    ，结果是在第一步中添加零

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

于 2019-11-21T07:12:20.133 回答