Previous: , Up: Multiplication Algorithms   [Index]

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.