位移操作的位成本

Question

位移操作的位成本

algorithmmathcomplexity-theorybit-manipulationbig-o

4

我之前更新了一个问题，但由于原问题已得到答复，所以我猜应该单独提出新问题。

以简单乘法算法为例。我在许多地方看到这样的说法：这是一项Log^2(N)操作。给出的解释是它由Log(N)个Log(N)数字相加组成。

我对此的问题在于，虽然这是正确的，但它忽略了每个Log(N)数字都将是位移的结果，到最后我们至少会进行Log(N)次位移。由于按位左移1是一项Log(N)操作，仅考虑位移就给我们带来了Log^2(N)操作。

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

事实上，任何移位和加法方法似乎都具有这种位数成本，而与加法的数量无关。

即使我们使用完美的最小位编码，任何M位乘N位的乘法都将导致约为M+N位数，因此必须至少将M+N位移N次才能输出/存储/组合项，这意味着最少需要执行N^2位操作。

这似乎与Toom-Cook等方法声称的操作数量相矛盾，请有人指出我的推理何处有误。

- Rhuaidhri Tynan

在像Toom-Cook这样的算法中，“移位”实际上并不是真正的移位。它只是添加到不同的内存地址。因此，这种“移位”是免费的。 - Mysticial

谢谢。只是为了确认一下，您是说Cook-Tombs中的移位是免费的，但在移位和加法方法中的移位不是免费的吗？ - Rhuaidhri Tynan

1

值得注意的是，如果我们谈论的是本地字大小，那么位移可能是O(1)（也许不完全是，但是当您处理完整个流水线和指令退役等等时，它可能就是了）。然而，如果我们谈论的是多字扩展精度整数库（或在软件中模拟硬件位移），那么位移很可能是与整数大小成正比的O(N)。 - twalberg

1

@RhuaidhriTynan 硬件中完成的移位不仅限于一次移动一个比特 - 合理使用各种电路组件可以使所有 N 个比特在一步中并行移动到其新位置，从而使其为 O(1)。在软件中执行此操作是不同的，这就是为什么多字算法必须是 O(N)（或者正如您所提到的那样，是 O(A)） - 您必须逐个处理每个字。被接受的答案更多地涉及能够将两个 O(N) 操作合并为一个仍然为 O(N) 的操作，而不是效率较低的算法可能表现不佳... - twalberg

我明白被接受的答案是什么，只是我表达得不好。现在我想了想，我明白为什么多字词会更昂贵，因为你不能只将所有单词向左移动1位，还必须担心一个比特是否需要从一个单词传递到下一个单词。如果我限制为本机字大小，那么指定移位的比特成本为O(1)是否可行？ - Rhuaidhri Tynan

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我认为解决这个问题的方法是您可以执行该操作。

 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的某些数字之和组成，而前导位可以通过任意进位传播来形成。总运行时间将与a和b中的数字数量以及需要进行移位的位置数量成比例。

真正的诀窍在于意识到您可以移动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）位操作更好。

希望这能有所帮助！