New n log n algorithm for high-precision multiplication

Niels Möller nisse at
Mon Apr 15 12:02:28 UTC 2019

paul zimmermann <Paul.Zimmermann at> writes:

> Schönhage-Strassen can be implemented with good cache locality:

Thanks! As I read it, for large inputs, the top level transforms operate
on coefficients that fit in L2 cache but not L1 cache, and with several
passes over the data, depending on fft size. Is that right?

Then I think small-prime fft has potential for better locality, with few
complete passes of the data and all the heavy fft work operating on data
in the L1 cache.


Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list