Those are absolutely incredible numbers. I know just how technically insane zn_poly is, so to be beating that by a factor of more than two, especially in the FFT range is *absolutely phenomenal*!!
I now feel a little bit embarrassed at only having said, "NTL is probably your best bet". On Tuesday, 11 September 2018 16:14:00 UTC+2, Victor Shoup wrote: > > I got curious, so I collected some data. Here are timing results > comparing NTL's zz_pX multiplication > to zn_poly's zn_array_mul. For various values of n, I multiplied > polynomials of degree < n > modulo a 50 bit number. The values of n are powers of 2 and halfway > between powers of 2, > ranging between 512 and 512K. > Both NTL and zn_poly were compiled using their default configurations. > Timings were done on a Skylake Xeon using gcc 8.2.0. > Each row reports n and the ratio (time for zn_poly)/(time for NTL). > So a ratio > 1 means NTL is faster. > > Also, by now, NTL implements a divide-and-conquer style truncated FFT, > using code some of which > is ultimately derived from some other code originally written by David > Harvey (fft62). > > 512 0.706683 > 768 0.84687 > 1024 0.922457 > 1536 0.923881 > 2048 1.02458 > 3072 0.982044 > 4096 1.0894 > 6144 1.32346 > 8192 1.33724 > 12288 1.61943 > 16384 1.44681 > 24576 1.35887 > 32768 1.43008 > 49152 1.34462 > 65536 1.40433 > 98304 1.48556 > 131072 1.42532 > 196608 1.3503 > 262144 1.43245 > 393216 1.61353 > > One can also compile NTL with an option that enables an AVX-based FFT > implementation. > With that option set, the numbers look like this. > > 512 1.30262 > 768 1.45693 > 1024 1.60583 > 1536 1.46475 > 2048 1.58405 > 3072 1.6219 > 4096 1.78167 > 6144 2.1571 > 8192 2 > 12288 2.52612 > 16384 2.25737 > 24576 2.25134 > 32768 2.32498 > 49152 2.28747 > 65536 2.15306 > 98304 2.52464 > 131072 2.18056 > 196608 2.22606 > 262144 2.13347 > 393216 2.56471 > > If anyone wants to the program I used for timing, let me know. > > On Friday, September 7, 2018 at 9:53:43 AM UTC-4, Erik Bray wrote: >> >> Hi all, >> >> Does anyone know what that current status is of the upstream zn_poly >> package? According to its website >> http://cims.nyu.edu/~harvey/zn_poly/ it is "no longer maintained", >> though it has been re-released under a BSD-compatible license. >> >> Since its last upstream release the package for it in Sage has >> accumulated a number of patches as well, and I believe I may need to >> add one more patch to it for building properly on Cygwin :( See >> https://trac.sagemath.org/ticket/26050 >> >> If it's alright, I would propose creating a new repository for it >> under the sagemath gitlab organization (or GitHub) which would become >> the new "upstream" for zn_poly. Then we can merge in all these >> patches; maybe even implement a new, more standard build system (I >> would be happy to do this). In fact the current "build system" is >> going to have problems long-term, as it currently consists primarily >> of a Python script that will not work, as written, on Python 3. >> > -- 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.
