manpagez: man pages & more
info gmp
Home | html | info | man
[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

15.1 Multiplication

NxN limb multiplications and squares are done using one of seven algorithms, as the size N increases.

AlgorithmThreshold
Basecase(none)
KaratsubaMUL_TOOM22_THRESHOLD
Toom-3MUL_TOOM33_THRESHOLD
Toom-4MUL_TOOM44_THRESHOLD
Toom-6.5MUL_TOOM6H_THRESHOLD
Toom-8.5MUL_TOOM8H_THRESHOLD
FFTMUL_FFT_THRESHOLD

Similarly for squaring, with the SQR thresholds.

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 section Unbalanced Multiplication).


This document was generated on March 31, 2014 using texi2html 5.0.

© manpagez.com 2000-2022
Individual documents may contain additional copyright information.