write new Integer_mod_dense class that wraps NTL directly

[sagetrac-dmharvey]

Currently Integer_mod_dense wraps the ZZX class in ntl.pyx. This causes a lot of overhead for small polynomials.

Component: basic arithmetic

Issue created by migration from https://trac.sagemath.org/ticket/528

[sagetrac-dmharvey]

comment:1

related: #331

[sagetrac-dmharvey]

Attachment: poly-int-dense1.hg.gz

moves Polynomial_integer_dense to cython

[sagetrac-dmharvey]

comment:2

The patch poly-int-dense1.hg moves Polynomial_integer_dense to a new cython file polynomial_integer_dense_ntl.pyx and renames the class to Polynomial_integer_dense_ntl, and minimal changes needed to make this build and pass tests.

This is the first step in addressing this ticket. Next step will be to change the underlying implementation to work with the NTL ZZX object directly instead of via ntl.pyx.

Already there's an improvement in overheads for arithmetic on small objects:

sage: R.<x> = PolynomialRing(ZZ)
sage: f = x^2 + x^3 - 5*x^4
sage: g = 47*x^2 + 3
sage: timeit h = f * g
10000 loops, best of 3: 23.8 µs per loop

vs

100000 loops, best of 3: 17.7 µs per loop

[robertwb]

comment:4

Some thoughts to consider:

• How far away is FLINT from doing the basic arithmetic at least? If it is close, how much effort should be spent on this?
• Is there anything to learn from the re-wrapping of NTL by Craig Citro and Joel Mohler?

[sagetrac-dmharvey]

comment:5

How far away is FLINT from doing the basic arithmetic at least? If it is close, how much effort should be spent on this?

I don't know. I am not working on FLINT presently due to lack of time. The amount of effort required to get FLINT to production standard appears to be way more than the time required to get this ticket done.

Is there anything to learn from the re-wrapping of NTL by Craig Citro and Joel Mohler?

Yes most definitely. I've discussed with this Joel, and I'll be studying that code before moving onto the next phase.

[williamstein]

comment:6

I've applied the bundle poly-int-dense1.hg to the official repo for the next SAGE release.

[sagetrac-dmharvey]

comment:7

I've added a patch patch-528.hg. This makes the Polynomial_integer_dense_ntl class talk directly to NTL, instead of wrapping an NTL object from ntl.pyx.

Also it adds many new doctests for polynomials over Z.

It's still pretty damn ugly though. Just the minimum to get the job done. A lot of work is still needed.

I think it basically works, but I wasn't able to run doctests properly because there are currently lots of other doctest failures in the repository.

[sagetrac-dmharvey]

comment:9

Note: patch-528.hg replaces an old version of the same name; it should be applied directly to sage 2.8.5. It also includes the patch for #738.

[sagetrac-dmharvey]

comment:10

hmmm that last patch is currently in conflict. Please ignore it for now; I'm going to work on a new one at SD5 anyway.

[sagetrac-dmharvey]

Attachment: patch-528.hg.gz

hopefully better now