Which algorithm does Java use for multiplication?

Question

The list of possible algorithms for multiplication is quite long:

• Schoolbook long multiplication
• Karatsuba algorithm
• 3-way Toom–Cook multiplication
• k-way Toom–Cook multiplication
• Mixed-level Toom–Cook
• Schönhage–Strassen algorithm
• Fürer's algorithm

Which one is used by Java by default and why? When does it switch to a "better performance" algorithm?

Answer 1

Well ... the * operator will use whatever the hardware provides. Java has no say in it.

But if you are talking about BigInteger.multiply(BigInteger), the answer depends on the Java version. For Java 11 it uses:

• naive "long multiplication" for small numbers,
• Karatsuba algorithm for medium sized number, and
• 3-way Toom–Cook multiplication for large numbers.

The thresholds are Karatsuba for numbers represented by 80 to 239 int values, an 3-way Toom-Cook for >= 240 int values. The smaller of the numbers being multiplied controls the algorithm selection.

---

Which one is used by Java by default and why?

Which ones? See above.

Why? Comments in the code imply that the thresholds were chosen empirically; i.e. someone did some systematic testing to determine which threshold values gave the best performance¹.

You can find more details by reading the source code².

---

^{1 - The current implementation BigInteger implementation hasn't changed significantly since 2013, so it is possible that it doesn't incorporate more recent research results.
2 - Note that this link is to the latest version on Github.}