问整数乘法真的是以现代CPU上的加法速度完成的吗？

EN

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

O(log )中的加法是通过将数字除以一半并(递归地)并行地添加两个部分来完成的，其中上半部分对于“0-进位”和“1-进位”情况都是求解的。一旦下半部分被添加，就会检查进位，并使用它的值在0进位和1进位之间进行选择。

O(log )深度的乘法也是通过并行化完成的，其中每三个数的和被简化为一个只有2个数的并行和，和是以类似于上述的方式完成的。

我不会在这里解释它，但是通过查找“进位”和“进位保存”加法，你可以找到关于快速加法和乘法的阅读材料。

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

整数乘法会变慢。

阿格纳福格(氏)指令表显示，当使用32位整数寄存器时，Haswell的ADD/SUB需要0.25个-1周期(取决于指令的流水线执行情况)，而MUL则需要2-4个周期。浮动点则相反: ADDSS/SUBSS周期为1-3周期，MULSS周期为0.5~5周期。

这是一个比简单的乘法和加法更复杂的答案。在现实中，答案很可能永远不会是肯定的。乘法，电子，是一个更复杂的电路。最主要的原因是，乘法是一个乘法步跟一个加法步骤的动作，记住在使用计算器之前乘以十进制数是什么样子。

另一件需要记住的是，乘法将花费更长或更短的时间，这取决于运行它的处理器的体系结构。这可能只是公司特有的，也可能不是简单的。虽然AMD很可能与英特尔不同，但即使是英特尔的i7也可能与核心2不同(在同一代内)，而且在不同代之间也有一定的不同(尤其是在你走得越远的时候)。

在所有技术上，如果乘法是您唯一要做的事情(不需要循环、计数等)，那么乘法将慢35倍(正如我在PPC体系结构上看到的那样)。这更多的是一个了解您的架构和电子产品的练习。

另外：：应该注意的是，可以为处理器构建一个处理器，其中包括一个乘法器，只需要一个时钟。这个处理器必须做的是，摆脱所有流水线，减慢时钟，使任何操作电路的HW延迟小于或等于时钟定时提供的延迟。

要做到这一点，就可以消除我们在处理器中添加流水线时所能获得的固有性能提高。流水线是一种将任务分解成更小的子任务，可以更快地执行的思想。通过在子任务之间存储和转发每个子任务的结果，我们现在可以运行一个更快的时钟速率，它只需要允许子任务的最长延迟，而不是从总体任务中运行。

乘积的时间图象：

|--------------------------------------------------|非流水线

第一步

在上面的图表中，非流水线电路需要50个单元的时间.在流水线版本中，我们将50个单元分成5个步骤，每个步骤花费10个单元的时间，其中一个存储步骤在两者之间。非常重要的是要注意，在流水线示例中，每个步骤都可以完全独立地并行工作。要完成一个操作，它必须按照顺序移动所有5个步骤，但是与操作数相同的另一个操作可以在步骤2中，就像在步骤1、3、4和5中一样。

所有这些都是这样的，这种流水线方法允许我们连续地填充每个时钟周期，并在每个时钟周期上得到一个结果，如果我们能够命令我们的操作，这样我们就可以在切换到另一个操作之前执行所有的操作，而我们作为计时命中的唯一方法就是将第一个操作从流水线中取出所需的时钟的原始数量。

神秘提出了另一个好的观点。从更多的系统角度来看待架构也是很重要的。诚然，较新的Haswell体系结构是为了改善处理器内的浮点乘法性能而构建的。由于这个原因，作为系统级别，它被设计成允许多个乘法同时发生，而一个添加只能在每个系统时钟中发生一次。

所有这些都可以概括为：

1. 每个体系结构都不同于较低级别的HW透视图，也不同于系统透视图。
2. 从功能上讲，乘法总是比添加花费更多的时间，因为它结合了一个真正的乘法和一个真正的加法步骤。
3. 了解您试图在其上运行代码的体系结构，并在可读性和从该体系结构获得最佳性能之间找到适当的平衡。