Bill, Above the diagonal, I believe Flint is using a Kronecker substitution algorithm, while NTL is using a multi-modular FFT. NTL always outperformed Flint in this region. It is the region below the diagonal where both are using Schoenhage-Strassen, and there you can see that NTL still lags behind Flint somewhat, though not as much as it used to.
The benchmark programs are available on the NTL web site, and I encourage anyone who wants to run similar benchmarks on a different platform to do so, and to verify that the benchmark software is fair. -Victor On Monday, July 9, 2018 at 8:33:12 AM UTC-4, Bill Hart wrote: > > 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.
