Previous: Other Multiplication, Up: Multiplication Algorithms   [Index]


16.1.7 Unbalanced Multiplication

Multiplication of operands with different sizes, both below MUL_KARATSUBA_THRESHOLD are done with plain schoolbook multiplication (see Basecase Multiplication).

For really large operands, we invoke the 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. These algorithms are denoted ToomMN where the first input is broken into M components and the second operand is broken into N components. MPIR currently implements Toom32, Toom33, Toom44, Toom53 and Toom8h which deals with a variety of sizes where the product polynomial will have length 15 or 16.