algorithm - 如果已经有硬件，为什么需要乘法算法？

我正在学习快速整数乘法的Karatsuba algorithm，并想知道，既然计算机已经在cpu中内置了专门的硬件来完成乘法，为什么需要这个算法？
是不是大数字很难乘法，但是算法把它分解成更简单的步骤，让硬件更容易处理，因为硬件擅长乘法较小的数字？

最佳答案

所有CPU都有固定的ALU/FPU位宽度。
例如，在i80x86（PC）上，ALU限制为：

i8086+   16 bit
i80386+  32 bit
x64 arch 64 bit

只允许计算16/32/64位数字作为操作数。i80x87 FPU使用80 bit数字表示，该数字表示由/转换为ieeefloat(32bit)/double(64bit)限制精度。
如果您需要计算具有较大位宽度的数字，则hw limit
然后，您需要将其分解为在alu/fpu上可计算的块（并将其作为数字处理），并将其结果组合到最终值。ALU是用这个来计数的，这就是为什么CPU有Carry标志并且ALU支持进位加法和减法现在如果你做的是简单的+/-，那么你只需把传播进位的从最低（lsw）到最高（msw）的所有数字加/减。见：
Cant make value propagate through carry
乘法和除法比较复杂，你需要使用长算法（比如你在纸上计算），这些算法通常O(n^2)。其中n是“位数”一个数字通常是8/16/32/64位数或其最大的10^m基数。当你在计算一些小的数字（高达100x位）时，更先进的算法就没有收益了，因为它们有太多的开销。对于更大的数字，形势会向他们倾斜见：
Fast bignum sqr
计算大浮点数是很棘手的，通常在整数算术运算器alu上，而不是在fpu上，运算速度更快。但在某些情况下，如果将值分解为更多变量（例如，为了在求和/积分时提高精度），您仍然可以从FPU中受益，请参见：
Is it possible to make realistic n-body solar system simulation in matter of size and mass?尤其是最后一次编辑

关于algorithm - 如果已经有硬件，为什么需要乘法算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35168928/