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