GNU Info

(gmp.info)Multiplication Algorithms

---

Next: Division Algorithms Prev: Algorithms Up: Algorithms

---

Enter node , (file) or (file)node

Multiplication
==============

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

     Algorithm      Threshold
     Basecase       (none)
     Karatsuba      `KARATSUBA_MUL_THRESHOLD'
     Toom-3         `TOOM3_MUL_THRESHOLD'
     FFT            `FFT_MUL_THRESHOLD'

   Similarly for squaring, with the `SQR' thresholds.  Note though that
the FFT is only used if GMP is configured with `--enable-fft', Note:
Build Options.

   NxM multiplications of operands with different sizes above
`KARATSUBA_MUL_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