3

我用这个更新了我之前问过的一个问题，但是当原始问题得到回答时，我猜我应该在一个新问题中单独问它。

以简单的乘法算法为例。我在很多地方看到声称这是一个 Log^2(N) 操作。给出的解释是，这是因为它由 Log(N) 和 Log(N) 数组成。

我遇到的问题是，虽然这是真的，但它忽略了这样一个事实，即每个 Log(N) 数字都是位移的结果，到最后我们将至少位移 Log(N) 次。由于位移 1 是一个 Log(N) 操作，因此单独考虑的位移会给我们 Log^2(N) 操作。

因此，当我看到它进一步声称实际上乘法实际上并不使用 Log^2(N) 运算时，这对我来说毫无意义，因为各种方法可以减少所需加法的数量。由于仅移位就给了我们 Log^2(N) 我对这种说法如何正确感到困惑。

事实上，无论有多少加法，任何移位和加法方法似乎都有这个位成本。

即使我们使用完美的最小位编码，任何 Mbit 乘 Nbit 乘法都会产生大约 M+Nbit 数，因此 M+N 位必须至少移动 N 次才能输出/存储/组合项，这意味着最小 N ^2 位操作。

这似乎与 Toom-Cook 等声称的操作数量相矛盾，所以有人可以指出我的推理存在缺陷的地方。

4

1 回答 1

3

我认为解决此问题的方法是您可以进行操作

 a + b << k

无需进行任何轮班。如果您想象添加会是什么样子，它看起来像这样：

  bn b(n - 1) ... b(n-k) b(n-k-1)     b0   0    ... 0  0  0  0
                  an     a(n-1)   ... ak a(k-1) ... a3 a2 a1 a0

换句话说，数字的最后 k 位将只是数字 a 的最后 k 位，中间数字将由 b 的数字子集和 a 的数字子集的总和组成，前导数字可以是通过对 b 的剩余数字进行任何进位的波纹传播形成。换句话说，总运行时间将与 a 和 b 中的位数以及进行移位的位置数成正比。

这里真正的诀窍是意识到您可以移动 k 个位置，而无需将 k 个单独的移动移动一个位置。与其将所有内容都洗牌 k 次，不如弄清楚这些位最终会在哪里结束并直接将它们写在那里。换句话说，移位 k 位的成本不是移位 1 位成本的 k 倍。它是 O(N + k)，其中 N 是数字中的位数。

因此，如果您可以根据一些“将两个数字相加”操作来实现乘法，则不必执行 O((log n) 2 ) 位操作。每个加法都进行 O(log n + k) 总位运算，因此如果 k 很小（例如 O(log n)）并且您只进行少量加法，那么您可以做得比 O((log n) 2）位操作。

希望这可以帮助！

于 2013-06-19T20:07:37.437 回答