Java默认采用何种乘法算法？为何选用该算法？何时切换至高性能乘法算法？

首先得明确：Java里的整数乘法分两种场景——int、long这类基本类型的乘法直接调用CPU硬件指令，只有java.math.BigInteger这种超大整数的乘法才会用到你列出的这些算法。咱们重点聊BigInteger的实现逻辑：

默认使用的算法 #

对于日常绝大多数中小规模的整数乘法，Java默认采用的是Schoolbook long multiplication（小学竖式乘法）。

为什么默认选它？ #

核心原因就两点：

• 实现简单易懂，代码维护成本极低；
• 对较小的整数（比如比特长度几百以内）来说，它的常数项开销远低于分治类算法（比如Karatsuba），实际运行速度更快。毕竟分治法需要拆分、递归、合并，这些步骤本身就有额外开销，只有当数字足够大时，分治法的时间复杂度优势才能盖过这些开销。

何时切换到“性能更优”的算法？ #

Java会根据要相乘的整数比特长度自动切换算法，不同JDK版本的阈值略有调整，以OpenJDK主流版本为例：

• 当操作数的比特长度超过Karatsuba算法阈值（通常是200~256位左右）时，会切换到Karatsuba algorithm。它的时间复杂度是O(n^{log₂3)≈O(n}1.585)，比小学乘法的O(n²)效率高很多，适合中等规模的大整数运算。
• 当操作数的比特长度进一步超过Schönhage–Strassen算法阈值（通常是2048~4096位左右）时，会切换到Schönhage–Strassen algorithm。这是基于FFT的算法，时间复杂度达到O(n log n log log n)，能轻松处理几千甚至上万位的超大整数乘法，此时分治法的效率已经跟不上了。

补充个小细节：你提到的Toom–Cook系列、Fürer's算法，目前OpenJDK的BigInteger实现里并没有默认启用——Toom–Cook的复杂度介于Karatsuba和Schönhage–Strassen之间，但实现复杂度高、常数项开销大，实际收益不如直接在两者间切换；而Fürer's算法理论上比Schönhage–Strassen更快，但目前还没有成熟的工业级实现，暂时没被纳入JDK标准库。

内容的提问来源于stack exchange，提问作者Lily