[flint-devel] Inclusion of zn_poly in FLINT

[Bill H. <goo...@go...>]

I've done a partial inclusion of zn_poly into FLINT (devel).

There is now a directory in FLINT called zn_poly, which contains a
largely unmodified copy of zn_poly-0.8. The FLINT makefile contains
lines to build the main zn_poly object files. These are linked
directly with FLINT when built, i.e. library calls to zn_poly are no
longer made.

I've set zmod_poly up to use the zn_poly polynomial multiplication
function. There is a #define at the top of zmod_poly.h called
USE_ZN_POLY, which will switch in the zn_poly code when it is defined
to be 1, otherwise all the original code is used.

I also made zmod_poly_mul_middle use zn_poly, though there seems to be
a difference between how the two libraries implement this. Basically
FLINT doesn't compute the first len1/2 coefficients whereas zn_poly
doesn't compute the first len2 - 1 coefficients. However FLINT has the
restriction that len2 - 1 < len1/2, thus by zeroing some of the
coefficients that come from zn_poly it is always possible to get the
same result as FLINT gives.

All the test functions in zmod_poly pass, and I actually ran a test
which compared the results of all multiplications whether top level or
subordinate between zn_poly and FLINT, and the results are always the
same. So this validates the multiplication functions in both FLINT and
zn_poly to a fairly high degree.

I cannot use the precomputed middle product functions yet, as FLINT is
set up to be able to use the same precomputed FFT for an ordinary
truncated multiplication and a middle product, whereas zn_poly-0.8
doesn't have ordinary truncated multiplication yet, as far as I can
see.

I may be able to use the zn_poly function for inverting a polynomial
however, which is the main place that the middle product is used. I'll
look into this tomorrow. Once that is done, zn_poly will basically be
used for everything it can be in FLINT at the moment. Below are
timings for the test code from before and after the inclusion of
zn_poly in FLINT. Note the zmod_poly_mul_middle test function was not
present before the inclusion. I added it to ensure that this function
returns the same thing before and after the inclusion.

Also note that functions such as mul_KS and mul_classical do not use
zn_poly. However all internal calls to such functions have been
replaced with calls to zn_poly where appropriate.

It's also important to realise that in many cases the majority of time
spent in the test code is not spent in the function that is being
tested. So even a small improvement in time of the test code
represents a large improvement in the time of the function being
tested.

Bill.

BEFORE:

Testing zmod_poly_to_from_string()... Cpu = 200 ms  Wall = 185 ms ... ok
Testing __zmod_poly_normalise()... Cpu = 170 ms  Wall = 175 ms ... ok
Testing zmod_poly_truncate()... Cpu = 170 ms  Wall = 167 ms ... ok
Testing zmod_poly_reverse()... Cpu = 300 ms  Wall = 305 ms ... ok
Testing zmod_poly_add_no_red()... Cpu = 80 ms  Wall = 77 ms ... ok
Testing zmod_poly_addsub()... Cpu = 60 ms  Wall = 62 ms ... ok
Testing zmod_poly_neg()... Cpu = 50 ms  Wall = 43 ms ... ok
Testing zmod_poly_bits()... Cpu = 10 ms  Wall = 17 ms ... ok
Testing zmod_poly_shift()... Cpu = 20 ms  Wall = 21 ms ... ok
Testing zmod_poly_swap()... Cpu = 30 ms  Wall = 22 ms ... ok
Testing zmod_poly_setequal()... Cpu = 10 ms  Wall = 18 ms ... ok
Testing _zmod_poly_attach()... Cpu = 10 ms  Wall = 9 ms ... ok
Testing _zmod_poly_attach_truncate()... Cpu = 10 ms  Wall = 9 ms ... ok
Testing _zmod_poly_attach_shift()... Cpu = 10 ms  Wall = 9 ms ... ok
Testing zmod_poly_derivative()... Cpu = 200 ms  Wall = 195 ms ... ok
Testing zmod_poly_getset_coeff()... Cpu = 10 ms  Wall = 10 ms ... ok
Testing zmod_poly_mul()... Cpu = 2660 ms  Wall = 2668 ms ... ok
Testing zmod_poly_mul_trunc_n()... Cpu = 3880 ms  Wall = 3876 ms ... ok
Testing zmod_poly_mul_classicalKS()... Cpu = 1290 ms  Wall = 1292 ms ... ok
Testing zmod_poly_sqr()... Cpu = 1970 ms  Wall = 1967 ms ... ok
Testing zmod_poly_sqr_classicalKS()... Cpu = 1030 ms  Wall = 1032 ms ... ok
Testing zmod_poly_mul_classical_trunc()... Cpu = 3220 ms  Wall = 3222 ms ... ok
Testing zmod_poly_mul_classical_trunc_left()... Cpu = 2200 ms  Wall =
2200 ms ... ok
Testing zmod_poly_mul_trunc_left_n()... Cpu = 2600 ms  Wall = 2601 ms ... ok
Testing zmod_poly_mul_KS_trunc()... Cpu = 1170 ms  Wall = 1168 ms ... ok
Testing zmod_poly_mul_KS_middle()... Cpu = 3850 ms  Wall = 3853 ms ... ok
Testing zmod_poly_mul_middle_precache()... Cpu = 2510 ms  Wall = 2509 ms ... ok
Testing _zmod_poly_mul_KS_precache()... Cpu = 3430 ms  Wall = 3427 ms ... ok
Testing zmod_poly_mul_precache()... Cpu = 7760 ms  Wall = 7762 ms ... ok
Testing zmod_poly_mul_trunc_n_precache()... Cpu = 7180 ms  Wall = 7179 ms ... ok
Testing zmod_poly_scalar_mul()... Cpu = 220 ms  Wall = 218 ms ... ok
Testing zmod_poly_make_monic()... Cpu = 440 ms  Wall = 440 ms ... ok
Testing zmod_poly_divrem_classical()... Cpu = 1640 ms  Wall = 1645 ms ... ok
Testing zmod_poly_divrem_newton()... Cpu = 2720 ms  Wall = 2717 ms ... ok
Testing zmod_poly_divrem()... Cpu = 10280 ms  Wall = 10275 ms ... ok
Testing zmod_poly_div_classical()... Cpu = 1870 ms  Wall = 1877 ms ... ok
Testing zmod_poly_div()... Cpu = 5760 ms  Wall = 5759 ms ... ok
Testing zmod_poly_divrem_divconquer()... Cpu = 1720 ms  Wall = 1722 ms ... ok
Testing zmod_poly_div_divconquer()... Cpu = 1950 ms  Wall = 1949 ms ... ok
Testing zmod_poly_div_divconquer_recursive()... Cpu = 1940 ms  Wall =
1935 ms ... ok
Testing zmod_poly_newton_invert_basecase()... Cpu = 530 ms  Wall = 531 ms ... ok
Testing zmod_poly_newton_invert()... Cpu = 9090 ms  Wall = 9091 ms ... ok
Testing zmod_poly_div_series()... Cpu = 1230 ms  Wall = 1231 ms ... ok
Testing zmod_poly_div_newton()... Cpu = 1270 ms  Wall = 1268 ms ... ok
Testing zmod_poly_gcd_euclidean()... Cpu = 6570 ms  Wall = 6572 ms ... ok
Testing zmod_poly_half_gcd_iter()... Cpu = 2310 ms  Wall = 2307 ms ... ok
Testing zmod_poly_gcd_hgcd()... Cpu = 6670 ms  Wall = 6667 ms ... ok
Testing zmod_poly_half_gcd()... Cpu = 1970 ms  Wall = 1974 ms ... ok
Testing zmod_poly_gcd()... Cpu = 3830 ms  Wall = 3835 ms ... ok
Testing zmod_poly_gcd_invert()... Cpu = 5190 ms  Wall = 5186 ms ... ok
Testing zmod_poly_xgcd()... Cpu = 4410 ms  Wall = 4413 ms ... ok
Testing zmod_poly_resultant_euclidean()... Cpu = 830 ms  Wall = 822 ms ... ok
Testing zmod_poly_mulmod()... Cpu = 2570 ms  Wall = 2572 ms ... ok
Testing zmod_poly_powmod()... Cpu = 4470 ms  Wall = 4470 ms ... ok
Testing zmod_poly_isirreducible()... Cpu = 4700 ms  Wall = 4704 ms ... ok
Testing zmod_poly_factor_berlekamp()... Cpu = 1720 ms  Wall = 1721 ms ... ok
Testing zmod_poly_factor_square_free()... Cpu = 2530 ms  Wall = 2525 ms ... ok
Testing zmod_poly_factor()... Cpu = 2910 ms  Wall = 2925 ms ... ok
Testing zmod_poly_2x2_mat_mul_classical_strassen()... Cpu = 790 ms
Wall = 783 ms ... ok
Testing zmod_poly_2x2_mat_mul()... Cpu = 2280 ms  Wall = 2285 ms ... ok

AFTER:

Testing zmod_poly_to_from_string()... Cpu = 180 ms  Wall = 184 ms ... ok
Testing __zmod_poly_normalise()... Cpu = 180 ms  Wall = 177 ms ... ok
Testing zmod_poly_truncate()... Cpu = 170 ms  Wall = 171 ms ... ok
Testing zmod_poly_reverse()... Cpu = 310 ms  Wall = 311 ms ... ok
Testing zmod_poly_add_no_red()... Cpu = 80 ms  Wall = 77 ms ... ok
Testing zmod_poly_addsub()... Cpu = 60 ms  Wall = 62 ms ... ok
Testing zmod_poly_neg()... Cpu = 50 ms  Wall = 43 ms ... ok
Testing zmod_poly_bits()... Cpu = 10 ms  Wall = 18 ms ... ok
Testing zmod_poly_shift()... Cpu = 20 ms  Wall = 21 ms ... ok
Testing zmod_poly_swap()... Cpu = 30 ms  Wall = 21 ms ... ok
Testing zmod_poly_setequal()... Cpu = 10 ms  Wall = 19 ms ... ok
Testing _zmod_poly_attach()... Cpu = 10 ms  Wall = 9 ms ... ok
Testing _zmod_poly_attach_truncate()... Cpu = 10 ms  Wall = 8 ms ... ok
Testing _zmod_poly_attach_shift()... Cpu = 10 ms  Wall = 10 ms ... ok
Testing zmod_poly_derivative()... Cpu = 200 ms  Wall = 197 ms ... ok
Testing zmod_poly_getset_coeff()... Cpu = 10 ms  Wall = 11 ms ... ok
Testing zmod_poly_mul()... Cpu = 2250 ms  Wall = 2247 ms ... ok
Testing zmod_poly_mul_trunc_n()... Cpu = 3960 ms  Wall = 3959 ms ... ok
Testing zmod_poly_mul_classicalKS()... Cpu = 1280 ms  Wall = 1286 ms ... ok
Testing zmod_poly_sqr()... Cpu = 1850 ms  Wall = 1849 ms ... ok
Testing zmod_poly_sqr_classicalKS()... Cpu = 1040 ms  Wall = 1036 ms ... ok
Testing zmod_poly_mul_classical_trunc()... Cpu = 3200 ms  Wall = 3202 ms ... ok
Testing zmod_poly_mul_classical_trunc_left()... Cpu = 2190 ms  Wall =
2190 ms ... ok
Testing zmod_poly_mul_trunc_left_n()... Cpu = 2440 ms  Wall = 2442 ms ... ok
Testing zmod_poly_mul_KS_trunc()... Cpu = 1170 ms  Wall = 1174 ms ... ok
Testing zmod_poly_mul_KS_middle()... Cpu = 3880 ms  Wall = 3873 ms ... ok
Testing zmod_poly_mul_middle()... Cpu = 3310 ms  Wall = 3311 ms ... ok
Testing zmod_poly_mul_middle_precache()... Cpu = 2320 ms  Wall = 2320 ms ... ok
Testing _zmod_poly_mul_KS_precache()... Cpu = 4200 ms  Wall = 4202 ms ... ok
Testing zmod_poly_mul_precache()... Cpu = 8210 ms  Wall = 8211 ms ... ok
Testing zmod_poly_mul_trunc_n_precache()... Cpu = 6700 ms  Wall = 6701 ms ... ok
Testing zmod_poly_scalar_mul()... Cpu = 220 ms  Wall = 217 ms ... ok
Testing zmod_poly_make_monic()... Cpu = 430 ms  Wall = 431 ms ... ok
Testing zmod_poly_divrem_classical()... Cpu = 1430 ms  Wall = 1430 ms ... ok
Testing zmod_poly_divrem_newton()... Cpu = 2620 ms  Wall = 2621 ms ... ok
Testing zmod_poly_divrem()... Cpu = 9420 ms  Wall = 9421 ms ... ok
Testing zmod_poly_div_classical()... Cpu = 1690 ms  Wall = 1689 ms ... ok
Testing zmod_poly_div()... Cpu = 5170 ms  Wall = 5172 ms ... ok
Testing zmod_poly_divrem_divconquer()... Cpu = 1430 ms  Wall = 1422 ms ... ok
Testing zmod_poly_div_divconquer()... Cpu = 1770 ms  Wall = 1775 ms ... ok
Testing zmod_poly_div_divconquer_recursive()... Cpu = 1770 ms  Wall =
1766 ms ... ok
Testing zmod_poly_newton_invert_basecase()... Cpu = 490 ms  Wall = 495 ms ... ok
Testing zmod_poly_newton_invert()... Cpu = 9720 ms  Wall = 9714 ms ... ok
Testing zmod_poly_div_series()... Cpu = 1230 ms  Wall = 1235 ms ... ok
Testing zmod_poly_div_newton()... Cpu = 1120 ms  Wall = 1121 ms ... ok
Testing zmod_poly_gcd_euclidean()... Cpu = 6600 ms  Wall = 6603 ms ... ok
Testing zmod_poly_half_gcd_iter()... Cpu = 2070 ms  Wall = 2069 ms ... ok
Testing zmod_poly_gcd_hgcd()... Cpu = 5590 ms  Wall = 5591 ms ... ok
Testing zmod_poly_half_gcd()... Cpu = 1780 ms  Wall = 1777 ms ... ok
Testing zmod_poly_gcd()... Cpu = 3280 ms  Wall = 3281 ms ... ok
Testing zmod_poly_gcd_invert()... Cpu = 4710 ms  Wall = 4709 ms ... ok
Testing zmod_poly_xgcd()... Cpu = 3850 ms  Wall = 3848 ms ... ok
Testing zmod_poly_resultant_euclidean()... Cpu = 860 ms  Wall = 857 ms ... ok
Testing zmod_poly_mulmod()... Cpu = 2370 ms  Wall = 2373 ms ... ok
Testing zmod_poly_powmod()... Cpu = 4000 ms  Wall = 4001 ms ... ok
Testing zmod_poly_isirreducible()... Cpu = 4380 ms  Wall = 4381 ms ... ok
Testing zmod_poly_factor_berlekamp()... Cpu = 1540 ms  Wall = 1536 ms ... ok
Testing zmod_poly_factor_square_free()... Cpu = 2980 ms  Wall = 2979 ms ... ok
Testing zmod_poly_factor()... Cpu = 2500 ms  Wall = 2508 ms ... ok
Testing zmod_poly_2x2_mat_mul_classical_strassen()... Cpu = 450 ms
Wall = 449 ms ... ok
Testing zmod_poly_2x2_mat_mul()... Cpu = 1510 ms  Wall = 1510 ms ... ok