Next: Division Algorithms, Previous: Algorithms, Up: Algorithms
NxN limb multiplications and squares are done using one of four algorithms, as the size N increases.
Algorithm Threshold Basecase (none) Karatsuba MUL_KARATSUBA_THRESHOLDToom-3 MUL_TOOM3_THRESHOLDFFT MUL_FFT_THRESHOLD
Similarly for squaring, with the SQR thresholds.
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.