Toom k-way in GMP 5?

Paul Zimmermann Paul.Zimmermann at loria.fr
Mon Jan 11 17:00:03 CET 2010


       Hi,

"info gmp" says for GMP 5.0.0:

   16.1.6 Other Multiplication
   ---------------------------

   The Toom algorithms described above (*note Toom 3-Way Multiplication::,
   *note Toom 4-Way Multiplication::) generalizes to split into an
   arbitrary number of pieces, as per Knuth section 4.3.3 algorithm C.
   This is not currently used.  The notes here are merely for interest.
   ^^^^^^^^^^^^^^^^^^^^^^^^^^

However "make tune" gives:

#define MUL_TOOM44_THRESHOLD               112
#define MUL_TOOM6H_THRESHOLD               254
#define MUL_TOOM8H_THRESHOLD               402

Which one is correct? Are the above thresholds unused?

Also later we can read:

   16.1.7 Unbalanced Multiplication
   --------------------------------

   ...

      For operands between these sizes, we use Toom inspired algorithms
   suggested by Alberto Zanoni and Marco Bodrato.  The idea is to split
   the operands into polynomials of different degree.  GMP currently
   splits the smaller operand onto 2 coefficients, i.e., a polynomial of
   degree 1, but the larger operand can be split into 2, 3, or 4
   coefficients, i.e., a polynomial of degree 1 to 3.

this suggests that only toom22, toom32 and toom42 are used, but:

#define MUL_TOOM32_TO_TOOM43_THRESHOLD      69
#define MUL_TOOM32_TO_TOOM53_THRESHOLD      76
#define MUL_TOOM42_TO_TOOM53_THRESHOLD      71
#define MUL_TOOM42_TO_TOOM63_THRESHOLD      78

Are the above thresholds unused?

Paul





More information about the gmp-devel mailing list