Re: [flint-devel] Inclusion of zn_poly in FLINT

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

I've now switched to zn_poly's newton inversion for polynomials of
length > 2000.

Times:

> BEFORE:

> Testing zmod_poly_divrem_newton()... Cpu = 2480 ms  Wall = 2487 ms ... ok
> Testing zmod_poly_divrem()... Cpu = 8510 ms  Wall = 8506 ms ... ok
> Testing zmod_poly_div_classical()... Cpu = 1160 ms  Wall = 1166 ms ... ok
> Testing zmod_poly_div()... Cpu = 4560 ms  Wall = 4561 ms ... ok
> Testing zmod_poly_divrem_divconquer()... Cpu = 1300 ms  Wall = 1307 ms ... ok
> Testing zmod_poly_div_divconquer()... Cpu = 1430 ms  Wall = 1431 ms ... ok
> Testing zmod_poly_div_divconquer_recursive()... Cpu = 1420 ms  Wall =
> 1421 ms ... ok
> Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 468 ms ... ok
> Testing zmod_poly_newton_invert()... Cpu = 9700 ms  Wall = 9699 ms ... ok
> Testing zmod_poly_div_series()... Cpu = 1200 ms  Wall = 1202 ms ... ok
> Testing zmod_poly_div_newton()... Cpu = 1090 ms  Wall = 1088 ms ... ok
> Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6300 ms ... ok
> Testing zmod_poly_half_gcd_iter()... Cpu = 1870 ms  Wall = 1868 ms ... ok
> Testing zmod_poly_gcd_hgcd()... Cpu = 5240 ms  Wall = 5243 ms ... ok
> Testing zmod_poly_half_gcd()... Cpu = 1630 ms  Wall = 1630 ms ... ok
> Testing zmod_poly_gcd()... Cpu = 3070 ms  Wall = 3068 ms ... ok
> Testing zmod_poly_gcd_invert()... Cpu = 4410 ms  Wall = 4410 ms ... ok
> Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3704 ms ... ok
> Testing zmod_poly_resultant_euclidean()... Cpu = 840 ms  Wall = 839 ms ... ok
> Testing zmod_poly_mulmod()... Cpu = 2340 ms  Wall = 2339 ms ... ok
> Testing zmod_poly_powmod()... Cpu = 3630 ms  Wall = 3629 ms ... ok
> Testing zmod_poly_isirreducible()... Cpu = 3730 ms  Wall = 3731 ms ... ok
> Testing zmod_poly_factor_berlekamp()... Cpu = 1390 ms  Wall = 1390 ms ... ok
> Testing zmod_poly_factor_square_free()... Cpu = 2740 ms  Wall = 2734 ms ... ok
> Testing zmod_poly_factor()... Cpu = 2360 ms  Wall = 2359 ms ... ok
>

AFTER:

Testing zmod_poly_divrem_newton()... Cpu = 2970 ms  Wall = 2970 ms ... ok
Testing zmod_poly_divrem()... Cpu = 9650 ms  Wall = 9655 ms ... ok
Testing zmod_poly_div_classical()... Cpu = 1170 ms  Wall = 1164 ms ... ok
Testing zmod_poly_div()... Cpu = 5240 ms  Wall = 5242 ms ... ok
Testing zmod_poly_divrem_divconquer()... Cpu = 1310 ms  Wall = 1316 ms ... ok
Testing zmod_poly_div_divconquer()... Cpu = 1440 ms  Wall = 1438 ms ... ok
Testing zmod_poly_div_divconquer_recursive()... Cpu = 1430 ms  Wall =
1430 ms ... ok
Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 469 ms ... ok
Testing zmod_poly_newton_invert()... Cpu = 8470 ms  Wall = 8466 ms ... ok
Testing zmod_poly_div_series()... Cpu = 1430 ms  Wall = 1430 ms ... ok
Testing zmod_poly_div_newton()... Cpu = 1400 ms  Wall = 1404 ms ... ok
Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6297 ms ... ok
Testing zmod_poly_half_gcd_iter()... Cpu = 1860 ms  Wall = 1862 ms ... ok
Testing zmod_poly_gcd_hgcd()... Cpu = 5270 ms  Wall = 5272 ms ... ok
Testing zmod_poly_half_gcd()... Cpu = 1620 ms  Wall = 1621 ms ... ok
Testing zmod_poly_gcd()... Cpu = 3090 ms  Wall = 3090 ms ... ok
Testing zmod_poly_gcd_invert()... Cpu = 4520 ms  Wall = 4520 ms ... ok
Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3693 ms ... ok
Testing zmod_poly_resultant_euclidean()... Cpu = 830 ms  Wall = 837 ms ... ok
Testing zmod_poly_mulmod()... Cpu = 2920 ms  Wall = 2915 ms ... ok
Testing zmod_poly_powmod()... Cpu = 3960 ms  Wall = 3966 ms ... ok
Testing zmod_poly_isirreducible()... Cpu = 3760 ms  Wall = 3754 ms ... ok
Testing zmod_poly_factor_berlekamp()... Cpu = 1400 ms  Wall = 1398 ms ... ok
Testing zmod_poly_factor_square_free()... Cpu = 3090 ms  Wall = 3091 ms ... ok
Testing zmod_poly_factor()... Cpu = 2640 ms  Wall = 2637 ms ... ok

I guess the FLINT crossover is wrong for zn_poly. The newton_invert
time went down, but the time for everything else that relies on it
went up. I'll have to have a fiddle this evening.

Bill.