16.1 Multiplication

NxN limb multiplications and squares are done using one of five algorithms, as the size N increases.

Algorithm	Threshold
Basecase	(none)
Karatsuba	MUL_TOOM22_THRESHOLD
Toom-3	MUL_TOOM33_THRESHOLD
Toom-4	MUL_TOOM44_THRESHOLD
FFT	MUL_FFT_THRESHOLD

Similarly for squaring, with the SQR thresholds.

NxM multiplications of operands with different sizes above MUL_TOOM22_THRESHOLD are currently done by special Toom-inspired algorithms or directly with FFT, depending on operand size (see section Unbalanced Multiplication).

This document was generated on February 16, 2012 using texi2html 5.0.