Speed up exact division in ℤ[x,y,...]

[mezzarobba]

...by directly calling Singular instead of first converting polynomials over ℚ (similar to #25287).

sage: p = 3*(-x^8*y^2 - x*y^9 + 6*x^8*y + 17*x^2*y^6 - x^3*y^2)
sage: q = 7*(x^2 + x*y + y^2 + 1)
sage: %timeit p//q # before
1000 loops, best of 3: 278 µs per loop
sage: %timeit p//q # after
The slowest run took 4.27 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 14.2 µs per loop

Note that this changes the result of some inexact divisions:

sage: P.<x,y> = ZZ[]
sage: (x+y)//(2*x) # before
0
sage: (x^3 + x^2 + 1)//(2*x)
0
sage: (x+y)//(2*x) # after
1
sage: (x^3 + x^2 + 1)//(2*x)
x^2 + x

But I frankly don't understand the definition that was used before; it seems that it was just an arbitrary choice of quotient that agreed with the exact result for exact divisions. In particular, neither the old definition nor the new one (nor // over ℚ) satisfies (p - (p//q)*q).lt() < p.lt().

Component: commutative algebra

Author: Marc Mezzarobba

Branch/Commit: ffb4507

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:2

At least for (x+y)//(2*x), I would (albeit naively) expect 0 since the monomial x//x == 1 and 1 * 2 == 0 (with certainly y*x == 0). However, it does make sense with quo_rem:

sage: (x+y).quo_rem(2*x)
(1, -x + y)
sage: (x^3+x^2+1).quo_rem(2*x)
(x^2 + x, -x^3 - x^2 + 1)

and it just returning the quotient.

[tscrim]

comment:3

Having thought more about it, I find the agreement with quo_rem to be more desirable. I also do not see the change in behavior as something people should be relying on and should be treated as a spacebar (even after this ticket). So positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[mezzarobba]

comment:4

Thanks!

[vbraun]

Changed branch from u/mmezzarobba/mpoly_div_ZZ to ffb4507