Raise an overflow error if the exponent of a multivariate polynomial flows over

[simon-king-jena]

The following happens at least since sage-4.6.2 and was detected in #4539 by a new doctest:

sage: P.<x,y> = QQ[]
sage: y^2^30
y^1073741824
sage: P.<x,y,z> = QQ[]
sage: y^2^30
0

According to Hans, the maximal exponent of a variable in a monomial does depend on the number of variables in the ring. There is no function that returns that maximal exponent, but it is stored in the bitmask attribute of a ring. The Singular interpreter actually only tests whether the total degree is below what is provided by bitmask; in theory, any exponent (not only the totall degree) can go up to that bound.

Here is the corresponding code in Singular's iparith.cc:

static BOOLEAN jjTIMES_P(leftv res, leftv u, leftv v)
{
  poly a;
  poly b;
  int dummy;
  if (v->next==NULL)
  {
    a=(poly)u->CopyD(POLY_CMD); // works also for VECTOR_CMD
    if (u->next==NULL)
    {
      b=(poly)v->CopyD(POLY_CMD); // works also for VECTOR_CMD
      if ((a!=NULL) && (b!=NULL)
      && (pTotaldegree(a)+pTotaldegree(b)>si_max((long)rVar(currRing),(long)currRing->bitmask)))
      {
        Werror("OVERFLOW in mult(d=%ld, d=%ld, max=%ld)",
          pTotaldegree(a),pTotaldegree(b),currRing->bitmask);
        pDelete(&a);
        pDelete(&b);
        return TRUE;
...

Apply

• attachment: trac11856_exponent_overflow.patch
• attachment: trac11856_fix_docs_32bit.patch

Depends on #10903

CC: @malb @burcin @alexanderdreyer @sagetrac-jakobkroeker

Component: commutative algebra

Keywords: exponent overflow

Author: Simon King

Reviewer: Martin Albrecht, Alexander Dreyer

Merged: sage-4.7.2.alpha4

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

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:1

The attached patch seems to solve the problem. It wraps the attribute bitmask of Singular's rings. Moreover, it detects exponent overflow in the same way as Singular does (see ticket description). rVar is in fact a macro that simply returns the ring->N attribute.

With the patch, I get (as a new doctest):

sage: P.<x,y> = QQ[]
sage: y^2^30
y^1073741824
sage: P.<x,y,z> = QQ[]
sage: y^2^30
Traceback (most recent call last):
...
OverflowError: Exponent overflow (1073741824).

I did not run the doc tests yet, but I think a reviewer can already have a look on it.

I wonder, though, whether the speed will be fine: I use the max function with the arguments being an unsigned long and a long. I can only hope that it is fast enough in Cython.

[malb]

comment:2

It seems max_exponent_size should be removed since it's not needed any more?

[simon-king-jena]

comment:3

I did some tests with Cython functions either testing whether (for cdefined a,b,c) we have a>max(b,c) or a>b and a>c. The execution time was about the same. So, the patch should be fine as it is (modulo doctests, of course).

I don't know whether max_exponent_size is used somewhere else.

[simon-king-jena]

comment:4

Very tricky. Singular correctly computes x<sup>2</sup>30*x<sup>2</sup>30, but it does not print it correctly, because when printing the exponent then it is converted in a different format:

sage: P.<x,y> = QQ[]
sage: (x^2^30*x^2^30)
x^-2147483648
sage: (x^2^30*x^2^30).degree()
2147483648

So, internally the degree is correct.

Even more tricky: In the case of x<sup>2</sup>31, Singular believes that the result is zero. The degree() method first tests whether it is (believed to be) zero, and acts accordingly:

sage: (x^2^31).degree()
-1
sage: (x^2^31)
0

That happens when I remove the max_exponent_size. I suppose I shouldd revert that removal...

[simon-king-jena]

comment:5

The latest patch version checks both whether the exponent exceeds max_exponent_size (which avoids some bugs that occur in Singular) and whether it is illegal in Singular (which avoids the bugs in Sage that led to the creation of this ticket).

We now have

        sage: x^2^30*x^2^30
        Traceback (most recent call last):
        ...
        OverflowError: Exponent overflow (2147483648).

I wonder whether the test, that became more expensive, led to an inacceptable speed regression. That should be investigated.

The tests in sage/rings/polynomial pass for me. I don't know about the rest. Needs review!

[malb]

comment:6

Code looks okay. So modulo the possible speed regression and doctests passing this should get a positive review.

[simon-king-jena]

comment:7

Here are some timings.

With the patch:

sage: P.<x,y,z> = QQ[]
sage: p = x+y
sage: %timeit q=p^20
625 loops, best of 3: 6.93 µs per loop
sage: p = x+y+z
sage: %timeit q=p^25
625 loops, best of 3: 418 µs per loop
sage: %timeit q=x^2^10
625 loops, best of 3: 2.1 µs per loop

Without the patch:

sage: P.<x,y,z> = QQ[]
sage: p = x+y
sage: %timeit q=p^20
625 loops, best of 3: 7.08 µs per loop
sage: p = x+y+z
sage: %timeit q=p^25
625 loops, best of 3: 419 µs per loop
sage: %timeit q=x^2^10
625 loops, best of 3: 2.14 µs per loop

These are only few data points, but they seem to show that the overhead is sufficiently small.