Previous: Other Multiplication, Up: Multiplication Algorithms

15.1.8 Unbalanced Multiplication

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.