New n log n algorithm for high-precision multiplication

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

> Schönhage-Strassen can be implemented with good cache locality:
>
> https://hal.inria.fr/inria-00126462

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.

Regards,
/Niels

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