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
Similarly for squaring, with the
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).
|• Basecase Multiplication|
|• Karatsuba Multiplication|
|• Toom 3-Way Multiplication|
|• Toom 4-Way Multiplication|
|• Higher degree Toom'n'half|
|• FFT Multiplication|
|• Other Multiplication|
|• Unbalanced Multiplication|