Node:Multiplication Algorithms, Next:Division Algorithms, Previous:Algorithms, Up:Algorithms

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

• Basecase Multiplication:
• Karatsuba Multiplication:
• Toom-Cook 3-Way Multiplication:
• FFT Multiplication:
• Other Multiplication: