Previous: Other Multiplication, Up: Multiplication Algorithms [Index]
Multiplication of operands with different sizes, both below
MUL_TOOM22_THRESHOLD
are done with plain schoolbook multiplication
(see Basecase Multiplication).
For really large operands, we invoke FFT directly.
For operands between these sizes, we use Toom inspired algorithms suggested by Alberto Zanoni and Marco Bodrato. The idea is to split the operands into polynomials of different degree. GMP currently splits the smaller operand onto 2 coefficients, i.e., a polynomial of degree 1, but the larger operand can be split into 2, 3, or 4 coefficients, i.e., a polynomial of degree 1 to 3.