These are ery interesting timings. In the region above the diagonal (and sufficiently far to the right - degree 12 I think), I believe we still use the SSA algorithm directly for polynomial arithmetic over Z. So your timings indicate that you are actually beating the Flint FFT directly.
This is quite remarkable given the work that went into it on in Flint (it was already significantly faster than the FFT's in Magma and GMP, and faster than the Gaudry, Kruppa, Zimmermann FFT. I congratulate you on what must be some truly impressive work. (I keep telling whoever will listen that we should spend some time trying to catch back up with the NTL benchmarks you have been publishing, but there seems to be little opportunity to work on such projects these days, and there seems to be a real shortage of young people taking on challenges like this. We do know what needs to be done. It's more an issue of finding people who could actually carry out the work.) Anyway, thanks again for the impressive work you've been doing on NTL, for making your code Open Source, so that we can all learn from it, and for the benchmarks you have been making available! Bill. On Saturday, 7 July 2018 20:39:59 UTC+2, Victor Shoup wrote: > > I just released NTL 11.2.0 at http://www.shoup.net/ntl > > The main change is a new and improved implementation of the > Schoenhage-Strassen FFT for multiplication of polynomials over the > integers. The new implementation includes a truncated FFT algorithm, the > "sqrt 2" trick, and better engineered low-level "butterfly" code. See > http://www.shoup.net/ntl/doc/tour-changes.html for details, including > some benchmarks. > > Also see http://www.shoup.net/ntl/benchmarks.pdf for an updated version > of NTL vs FLINT report. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
