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