GMP 4.3 multiplication performance

Niels Möller nisse at
Thu Jun 4 12:43:35 CEST 2009

Torbjorn Granlund <tg at> writes:

> For toomNN, the symmetric cases, we should have a single function for
> evaluation, used for both operands of toom44_mul, and for the single
> operand of toom4_sqr?

I don't think it's a good idea to have a function that evaluates a
degree 3 polynomial in *all* points. By interleaving evaluation and
multiplication, one can reduce the storage need.

I do think it does make a lot of sense to have a functions for
evaluation in pairs of points, +1, -1, +2, -2, etc. These evaluations
should be done together, since there are common expressions, even if
it costs some storage.

Evaluatiion functions for point pairs are also more generally useful,
not just for toom44_mul and toom4_sqr, but also for toomX4_mul and
maybe also toom4X_mul (unless it turns out that the function call
overhead is unacceptable for toom43 and toom42, in which case I think
it would be nice if we can somehow reuse the same functions but
arrange to have the calls inlined).


More information about the gmp-devel mailing list