c - C 是否在内部使用 Karatsuba 算法将两个整数相乘？

Question

当 C 将两个 n 位 整数相乘时，它在内部使用普通的 O(n^2) 乘法算法，还是使用 Karatsuba 的变体 O(n^log_2(3)) 乘法算法 ?

Answer 1

没有。 Karatsuba 算法的“簿记”开销太高太复杂。它会比乘法器占用更多的硅，即使它要在机器字级别上实现收支平衡的递归深度。对于足够大的 n，硬件加密加速器或 FPGA 可能值得。即便如此，收支平衡点可能太高而无法满足加密需求。天下没有免费的午餐。

另一方面，我们可以查看 GMP library 中的 gmp-mparam.h 文件，它定义了 阈值 值，在该值处渐近更快的算法实际上开始得到返回。 'Karatsuba' 是更通用的 Toom-Cook 算法的 2x2 情况。即使在像 Broadwell 和 Skylake CPU 这样的怪物上，阈值也在 28 个“字”或 1792 位左右。这是由于(递归地)将 3 个结果与进位传播加在一起的开销。随着乘法指令吞吐量的增加，这些阈值将不断提高。