Next: Division Algorithms, Previous: Algorithms, Up: Algorithms [Index]
NxN limb multiplications and squares are done using one of six algorithms, as the size N increases.
Algorithm Mul Threshold Basecase (none) Karatsuba MUL_KARATSUBA_THRESHOLD
Toom-3 MUL_TOOM3_THRESHOLD
Toom-4 MUL_TOOM4_THRESHOLD
Toom-8(.5) MUL_TOOM8H_THRESHOLD
FFT MUL_FFT_FULL_THRESHOLD
Algorithm Sqr Threshold Basecase (none) Karatsuba SQR_KARATSUBA_THRESHOLD
Toom-3 SQR_TOOM3_THRESHOLD
Toom-4 SQR_TOOM4_THRESHOLD
Toom-8 SQR_TOOM8_THRESHOLD
FFT SQR_FFT_FULL_THRESHOLD
NxM multiplications of operands with different sizes above
MUL_KARATSUBA_THRESHOLD
are done using unbalanced Toom algorithms or
with the FFT. See (see Unbalanced Multiplication).
• Basecase Multiplication: | ||
• Karatsuba Multiplication: | ||
• Toom 3-Way Multiplication: | ||
• Toom 4-Way Multiplication: | ||
• FFT Multiplication: | ||
• Other Multiplication: | ||
• Unbalanced Multiplication: |