Next: Division Algorithms, Previous: Algorithms, Up: Algorithms [Index]
NxN limb multiplications and squares are done using one of seven algorithms, as the size N increases.
Algorithm Threshold Basecase (none) Karatsuba MUL_TOOM22_THRESHOLD
Toom-3 MUL_TOOM33_THRESHOLD
Toom-4 MUL_TOOM44_THRESHOLD
Toom-6.5 MUL_TOOM6H_THRESHOLD
Toom-8.5 MUL_TOOM8H_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 Unbalanced Multiplication).