algorithm - 如果硬件已经做到了，为什么还需要乘法算法？

Question

我正在了解 Karatsuba algorithm用于快速整数乘法并想知道，既然计算机已经在 CPU 中内置了专用硬件来进行乘法运算，为什么还需要这种算法？

是不是大数很难相乘，但算法将其分解为更简单的步骤，硬件更容易处理，因为硬件擅长乘以较小的数？

Answer 1

1. 所有 CPU 的 ALU/FPU 位宽都是固定的。

   例如在i80x86 (PC) 上 ALU 限制为:

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

   仅允许计算最多 16/32/64 位数字作为操作数。 i80x87 FPU 使用从/到 IEEE float(32bit)/double(64bit) 转换的 80 位 数字表示> 限制精度。

2. 如果您需要计算位宽大于硬件限制的数字

   然后您需要将其分解为可在 ALU/FPU 上计算的 block (并将它们作为数字的数字处理)并将它们的结果合并为最终值。 ALU 以此计数，这就是为什么 CPU 具有 进位 标志并且 ALU 支持带进位的加法和减法。现在，如果您正在执行简单的 +/-，那么您只需添加/替换从最低 (LSW) 到最高 (MSW) 的所有数字以传播进位。见:

   • Cant make value propagate through carry

   乘法和除法比较复杂，你需要使用很长的算法(就像你在纸上计算)，通常是 O(n^2)。其中 n 是“数字”的数量。一个数字通常是8/16/32/64 位数或其最大的10^m 基数。当您计算小数字(最多 100 倍位)时，使用更高级的算法不会有任何好处，因为它们的开销太大。对于更大的数字，情况对他们有利。见:

   • Fast bignum sqr

   计算大的 float 是很棘手的，通常在 ALU 上而不是在 FPU 上完成整数运算通常更快。但在某些情况下，如果您将值分解为更多变量，例如在求和/积分时提高准确性，您仍然可以从 FPU 中受益，请参阅:

   • Is it possible to make realistic n-body solar system simulation in matter of size and mass?尤其是最后一次编辑