Codelets for ToomN1 (for N=2, 3, 4, 6, 8) should be added and here's why. (Also: a significant non-triviality on where cut-off points should be).

Marco Bodrato bodrato at
Thu Apr 5 21:33:15 UTC 2018

Dear Paul,

Il Mer, 4 Aprile 2018 9:52 am, paul zimmermann ha scritto:
> One possible interpretation is the following: the simple threshold
> mechanism used by GMP might be suboptimal.

We know ;-)

> Since MUL_TOOM8H_THRESHOLD=214 on my computer, you don't need to have a
> large table to cover all Toom variants.

By the way, in the last message I forgot to point to some graphs we
elaborated to show where each multiplication variant is better. They can
be found at, under the title "New Toom
multiplication code for unbalanced operands".
Those graphs are old, they did not yet take into account either Toom6h or

> However, for the unbalanced multiplication, one would need a
> bi-dimensional table, which would be more expensive to store.

Should we really stop the bi-dimensional table at Toom8h? What about the
dispersed border Toom-versus-FFT?

Maybe a more fine-grained table for small sizes... then another table for
larger values.. We shall thinkabout that.



More information about the gmp-discuss mailing list