Toom k-way in GMP 5?

bodrato at bodrato at
Mon Jan 11 18:42:32 CET 2010


You spotted a bug in the documentation.

In GMP-5.0.0, balanced multiplication uses Toom-2 (aka. Karatsuba),
Toom-3, Toom-4, Toom-6 and Toom-8. For bigger operands, fft_mul is used
(currently the product mod B^n-1, waiting for a better SS or NTT...)

For very unbalanced operands: toom42, toom63 or fft_mul are iterated.

For moderated unbalancements, there are explicit calls to the balanced
variants above, the aforementioned iterated methods, plus toom32, toom43
and toom53.

One more note: Toom-6 and Toom-8 implementations are integrated in the two
functions mpn_toom6h_mul, and mpn_toom8h_mul respectively. Those function
decide internally the actual split-strategy... in the range where they are
used, toom6h can implicitly use the 6x6, 7x6, or 7x5 split; toom8h can
actually be 8x8, 9x8, and 9x7.

Best regards,


More information about the gmp-devel mailing list