caching of transforms used for large multiplications

Daniel Lichtblau danl at
Tue Jun 11 22:32:22 CEST 2013

[This is a slightly revised version of a question I raised in
direct email. Sending to list per moderator suggestion. Possibly
I should have known to do that to begin with, but there was a
nagging suspicion that the question might be off base.]

This is in regard to operations that arise with asymptotically
fast gcd algorithms. They may have relevance elsewhere as well.
Niels Moeller remarks about the underlying idea in talk slides
from a few years back. There are various bignum multiplications
where a multiplicand may be used in more than one product. In
situations where the numbers are sufficiently large presumably
NTT or some related FFT-based method is used.

My question(s): Are these NTT intermediate results cached? If
not, is there a way to "tell" GMP to keep them around for
subsequent reuse? I suspect such caching might be a generally
useful thing to have if it is not already present. For fast
GCD it could amount to a notable speed gain, I think. I
believe Niels remarked specifically on this but do not have
the reference at hand, so I defer to him for details in case
estimates or actual timings were done on this.

Daniel Lichtblau

More information about the gmp-devel mailing list