Next: , Previous: Algorithms, Up: Algorithms

15.1 Multiplication

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).