Java 使用哪种算法进行乘法运算？

Question

可能的乘法算法列表很长：

• 教科书长乘法
• Karatsuba 算法
• 3 次 Toom–Cook 乘法
• k 向 Toom–Cook 乘法
• 混合级别的 Toom–Cook
• Schönhage–Strassen 算法
• 富勒的算法

Java 默认使用哪个，为什么？它什么时候切换到 “更好的性能” 算法？

Answer 1

嗯... * 操作员将使用硬件提供的任何内容。 Java 没有发言权。

但是如果你说的是BigInteger.multiply(BigInteger)，答案取决于Java版本。对于 Java 11，它使用：

• 小数的天真“长乘法”，
• 中型数字的 Karatsuba 算法，
• 大数的三向 Toom–Cook 乘法。

对于由 80 到 239 int 值表示的数字，阈值为 Karatsuba，对于 >= 240 int 值，阈值为 3 向 Toom-Cook。相乘的数字中较小的数字控制算法选择。

---

Which one is used by Java by default and why?

哪些？见上文。

为什么？代码中的注释暗示阈值是根据经验选择的；即有人做了一些系统测试以确定哪些阈值提供最佳性能¹.

您可以通过阅读 source code².

了解更多详情

---

^{1 - 当前的实施 BigInteger 自 2013 年以来实施没有发生重大变化，因此它可能没有包含更多的最新研究结果。
2 - 请注意，此 link 是 最新的 版本 Github.}