16.1 Multiplication

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

Algorithm	Mul Threshold
Basecase	(none)
Karatsuba	MUL_KARATSUBA_THRESHOLD
Toom-3	MUL_TOOM3_THRESHOLD
Toom-4	MUL_TOOM4_THRESHOLD
Toom-8(.5)	MUL_TOOM8H_THRESHOLD
FFT	MUL_FFT_FULL_THRESHOLD

Algorithm	Sqr Threshold
Basecase	(none)
Karatsuba	SQR_KARATSUBA_THRESHOLD
Toom-3	SQR_TOOM3_THRESHOLD
Toom-4	SQR_TOOM4_THRESHOLD
Toom-8	SQR_TOOM8_THRESHOLD
FFT	SQR_FFT_FULL_THRESHOLD

NxM multiplications of operands with different sizes above MUL_KARATSUBA_THRESHOLD are done using unbalanced Toom algorithms or with the FFT. See (see Unbalanced Multiplication).