Next: , Previous: Algorithms, Up: Algorithms   [Index]


16.1 Multiplication

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

AlgorithmMul Threshold
Basecase(none)
KaratsubaMUL_KARATSUBA_THRESHOLD
Toom-3MUL_TOOM3_THRESHOLD
Toom-4MUL_TOOM4_THRESHOLD
Toom-8(.5)MUL_TOOM8H_THRESHOLD
FFTMUL_FFT_FULL_THRESHOLD
AlgorithmSqr Threshold
Basecase(none)
KaratsubaSQR_KARATSUBA_THRESHOLD
Toom-3SQR_TOOM3_THRESHOLD
Toom-4SQR_TOOM4_THRESHOLD
Toom-8SQR_TOOM8_THRESHOLD
FFTSQR_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).