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.
