(gmp.info.gz) Multiplication Algorithms

Info Catalog

(gmp.info.gz) Algorithms

(gmp.info.gz) Algorithms

(gmp.info.gz) Division 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.
 
    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.
 

Menu

 
* Basecase Multiplication
* Karatsuba Multiplication
* Toom 3-Way Multiplication
* FFT Multiplication
* Other Multiplication
 

Info Catalog

(gmp.info.gz) Algorithms

(gmp.info.gz) Algorithms

(gmp.info.gz) Division Algorithms