整数乘法真的以与现代CPU上的加法相同的速度完成吗？

Question

我经常听到这种说法，现代硬件上的乘法非常优化，实际上它的速度与加法相同。这是真的吗？

我从来没有得到过任何权威的确认。我自己的研究只增加了问题。速度测试通常显示的数据让我感到困惑。以下是一个示例：

#include <stdio.h>
#include <sys/time.h>

unsigned int time1000() {
    timeval val;
    gettimeofday(&val, 0);
    val.tv_sec &= 0xffff;
    return val.tv_sec * 1000 + val.tv_usec / 1000;
}

int main() {
    unsigned int sum = 1, T = time1000();
    for (int i = 1; i < 100000000; i++) {
        sum += i + (i+1); sum++;
    }
    printf("%u %u\n", time1000() - T, sum);
    sum = 1;
    T = time1000();
    for (int i = 1; i < 100000000; i++) {
        sum += i * (i+1); sum++;
    }
    printf("%u %u\n", time1000() - T, sum);
}

上面的代码可以显示乘法更快：

clang++ benchmark.cpp -o benchmark
./benchmark
746 1974919423
708 3830355456

但是对于其他编译器，其他编译器参数，不同编写的内部循环，结果可能不同，我甚至不能得到一个近似值。

Answer 1

这是一个比简单的乘法与加法更复杂的答案。实际上，答案很可能永远不会是肯定的。乘法，在电子学上，是一个更复杂的电路。大多数原因，是乘法是乘法步骤后加法步骤的行为，请记住在使用计算器之前乘以十进制数的感觉。

另一件要记住的事情是，乘法运算需要的时间长短取决于运行它的处理器的架构。这可能是也可能不是公司特有的。虽然AMD最有可能与Intel不同，但即使是Intel i7也可能与core 2不同(在同一代内)，而且不同代之间肯定也不同(尤其是追溯到更久远的年代)。

从技术上来说，如果乘法是你唯一要做的事情(没有循环，计数等等)...)，乘法会慢2到35倍(正如我在PPC架构上看到的)。这更多的是一个理解你的html" target="_blank">架构和电子的练习。

此外：应该注意的是，可以构建一个处理器，包括乘法在内的所有操作都需要一个时钟。该处理器必须做的是，摆脱所有流水线，并减慢时钟，以便任何OP电路的硬件延迟小于或等于时钟时序提供的延迟。

这样做可以消除在处理器中添加流水线时固有的性能提升。流水线是指将一个任务分解为更小的子任务，这样可以更快地执行。通过在子任务之间存储和转发每个子任务的结果，我们现在可以运行更快的时钟频率，只需要允许子任务的最长延迟，而不需要从总体任务开始。

通过乘法来描绘时间：

| - |非流水线

|--步骤1--|--步骤2--|--步骤3--|--步骤4--|--步骤5--|流水线

在上图中，非流水线电路需要50个单位的时间。在流水线版本中，我们将 50 个单元拆分为 5 个步骤，每个步骤需要 10 个单元的时间，中间有一个存储步骤。非常重要的是要注意，在流水线示例中，每个步骤都可以完全独立且并行工作。要完成一个操作，它必须按顺序遍历所有 5 个步骤，但另一个具有操作数的相同操作可以在步骤 2 中，就像步骤 1、3、4 和 5 中的操作一样。

综上所述，这种流水线方法允许我们在每个时钟周期持续填充操作员，如果我们能够对操作进行排序，以便在切换到另一个操作之前执行所有操作，则可以在每个时钟循环上获得结果，我们所要做的就是将FIRST操作从流水线中取出所需的原始时钟量。

神秘带来了另一个好观点。从更系统的角度来看架构也很重要。的确，新的Haswell架构是为了提高处理器内的浮点乘法性能而构建的。由于这个原因，作为系统级，它的架构允许同时发生多次乘法，而不是每个系统时钟只能发生一次加法。

所有这些都可以总结如下：

1. 从较低级别的硬件角度以及从系统角度来看，每个架构都不同
2. 从功能上讲，乘法总是比加法花费更多的时间，因为它将真乘法与真加法步骤结合在一起。
3. 了解您尝试运行代码的架构，并在易读性和从该架构获得真正最佳性能之间找到适当的平衡。

Answer 2

整数乘法会慢一些。

Agner Fog的指令表显示，当使用32位整数寄存器时，Haswell的ADD/SUB需要0.25–1个周期（取决于指令的管道化程度），而MUL需要2–4个周期。浮点则相反：ADDSS/SUBSS需要1–3个周期，而MULSS需要0.5–5个周期。

Answer 3

两个n位数的乘法实际上可以在O(log n)电路深度内完成，就像加法一样。

O（log n）中的加法是通过将数字对半拆分并（递归地）并行添加两部分来完成的，其中上半部分是针对“0进位”和“1进位”情况求解的。一旦添加了下半部分，就会检查进位，并使用其值在0进位和1进位情况之间进行选择。

O(log n)深度的乘法也是通过并行化来完成的，其中3个数的每一个和被简化为并行的2个数的和，并且这些和是以类似于上述的某种方式来完成的。< br >这里就不解释了，但是你可以通过查“进位-前瞻”和“进位-保存”加法找到关于快速加法和乘法的阅读材料。

因此，从理论角度来看，由于电路显然是内在并行的（与软件不同），乘法渐近较慢的唯一原因是前面的常数，而不是渐近复杂性。