caching of transforms used for large multiplications

Daniel Lichtblau danl at
Wed Jun 12 19:57:26 CEST 2013

Niels, Torbjorn,

Thank you both for your detailed responses.

Re GCD usage, mostly I had in mind the matrix multiplications
(which I believe are balanced) and a few others that, if memory
serves, are not woefully unbalanced. Possibly one value would be
a factor of two larger in size than the other (i.e. the smaller
on the order of the square root of the bigger). This might be
what Niels had in mind with "splitting the larger factor..." Also
there are cases where one factor is used in more than one product,
and caching the transform might then be helpful regardless of size.
That said, Torbjorn's response gave some reasons why it might be
less of a gain than I had thought.

I made the journey into my filing cabinets to find the reference.
I located my HGCD folder somewhere past what appears to be the
shrunken head of a former coworker (I don't recall having put that
there. Really.) It was indeed Niels' "Subquadratic GCD", dated
October 30, 2008-- did not say where the presentation was given
but it could well be an update of the slides referred to in Niels'


More information about the gmp-devel mailing list