GNU MP 4.1.2
16.1 Multiplication
NxN limb multiplications and squares are done using one of four
algorithms, as the size N increases.
| Algorithm | Threshold |
| Basecase | (none) |
| Karatsuba | MUL_KARATSUBA_THRESHOLD |
| Toom-3 | MUL_TOOM3_THRESHOLD |
| FFT | MUL_FFT_THRESHOLD |
Similarly for squaring, with the SQR thresholds. Note though that the
FFT is only used if GMP is configured with `--enable-fft', see section 2.1 Build Options.
NxM multiplications of operands with different sizes above
MUL_KARATSUBA_THRESHOLD are currently done by splitting into MxM
pieces. The Karatsuba and Toom-3 routines then operate only on equal size
operands. This is not very efficient, and is slated for improvement in the
future.
