algorithm - 位移位的位成本

Question

我用这个更新了我之前问过的一个问题，但是由于原来的问题得到了回答，我猜我应该在一个新问题中单独提出这个问题。

以简单的乘法算法为例。我在许多地方看到声称这是一个 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 等声称的操作次数相矛盾，所以请有人指出我的推理有缺陷的地方。

Answer 1

我认为解决这个问题的方法是您可以进行手术

 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)²) 位操作.每次加法执行 O(log n + k) 总位操作，因此如果 k 很小(比如 O(log n))并且你只做少量加法，那么你可以比 O((log n) ²) 位运算。

希望这对您有所帮助!