Opened 7 years ago

Closed 7 years ago

Last modified 4 years ago

#11856 closed defect (fixed)

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

Reported by: SimonKing Owned by: malb
Priority: critical Milestone: sage-4.7.2
Component: commutative algebra Keywords: exponent overflow
Cc: malb, burcin, AlexanderDreyer, jakobkroeker Merged in: sage-4.7.2.alpha4
Authors: Simon King Reviewers: Martin Albrecht, Alexander Dreyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10903 Stopgaps:

Description (last modified by jdemeyer)

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

Attachments (2)

trac11856_fix_docs_32bit.patch (1.1 KB) - added by SimonKing 7 years ago.
Alexander 's reviewer patch
trac11856_exponent_overflow.patch (5.9 KB) - added by SimonKing 7 years ago.
Mimmick Singular's exponent overflow check but still avoids some bugs that Singular provides

Download all attachments as: .zip

Change History (30)

comment:1 Changed 7 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_review

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.

comment:2 Changed 7 years ago by malb

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

comment:3 Changed 7 years ago by SimonKing

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.

comment:4 Changed 7 years ago by SimonKing

Very tricky. Singular correctly computes x^2^30*x^2^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^2^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...

comment:5 Changed 7 years ago by SimonKing

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!

comment:6 Changed 7 years ago by malb

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

comment:7 Changed 7 years ago by SimonKing

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.

comment:8 Changed 7 years ago by malb

  • Status changed from needs_review to positive_review

comment:9 Changed 7 years ago by davidloeffler

  • Reviewers set to Martin Albrecht

comment:10 follow-up: Changed 7 years ago by SimonKing

  • Cc malb burcin AlexanderDreyer added; malb burcin removed
  • Status changed from positive_review to needs_info

Alexander found (while reviewing #4539) that the patch from here results in two doctest errors on 32-bit machines (reasonable, since an overflow error will occur earlier on 32 bit than on 64 bit).

He provided a fix at #4539, but actually I think it should be included here. What do people think?

comment:11 Changed 7 years ago by SimonKing

  • Work issues set to 32bit doctests

comment:12 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by AlexanderDreyer

Replying to SimonKing:

He provided a fix at #4539, but actually I think it should be included here. What do people think?

Indeed, I also had to apply http://trac.sagemath.org/sage_trac/attachment/ticket/4539/trac4539_fix_docs_32bit.patch here for 32-bit systems. So, I think, it is necessary.

BTW: it seems that this ticket depends on #11115.

comment:13 in reply to: ↑ 12 Changed 7 years ago by SimonKing

Replying to AlexanderDreyer:

Replying to SimonKing: BTW: it seems that this ticket depends on #11115.

What ticket are you referring to by "this"? If "this" is #4539: #4539 depends on #11068, which depends on #11115. But if "this" is #11856 then I don't see a dependency. What do you mean? Is there fuzz when applying my or your patch? Does it not work without #11115?

comment:14 Changed 7 years ago by SimonKing

  • Status changed from needs_info to needs_review

I just tested: trac11856_exponent_overflow.patch followed by trac4539_fix_docs_32bit.patch cleanly applies to sage-4.7.2.alpha3-prerelease.

Thus, if Alexander finds that trac4539_fix_docs_32bit.patch fixes the problem on 32-bit (I can not test it, myself), then I suggest that Alexander's patch should be moved from #4539 to here and turned into a reviewer patch; and if Alexander says that it is fixed, then we should return to a positive review.

comment:15 Changed 7 years ago by AlexanderDreyer

  • Reviewers changed from Martin Albrecht to Martin Albrecht, Alexander Dreyer
  • Status changed from needs_review to positive_review

Indeed, I thought that #11856 would depend on #11115. But it turned out, that my Sage becomes corrupted when popping the patches of. #11115. So starting with a brand new clone of devel/sage-main does the trick.

So I can confirm, http://trac.sagemath.org/sage_trac/attachment/ticket/4539/trac4539_fix_docs_32bit.patch fixes the problem on 23 Bit platforms.

comment:16 Changed 7 years ago by AlexanderDreyer

..32 Bit ... ;-)

Changed 7 years ago by SimonKing

Alexander 's reviewer patch

comment:17 Changed 7 years ago by SimonKing

  • Description modified (diff)

Let's try to sort things out:

The patch that Alexander posted at #4539 should better be a reviewer patch here. Thus, I copied his patch, added a commit message, and posted it here under a new name reflecting the ticket number. The positive review can be kept (I hope we agree on that), and:

Apply trac11856_exponent_overflow.patch trac11856_fix_docs_32bit.patch

comment:18 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Work issues 32bit doctests deleted

comment:19 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to Conflict with #11339

This seems to conflict with #11339.

comment:20 Changed 7 years ago by SimonKing

  • Status changed from needs_work to positive_review

The first patch has been rebased on top of #11339. The patch from #11339 did some cosmetic changes, such as replacing p_Delete(&p,r) by p_Delete(&p, r). Therefore, one of the hunks from the first patch here did not apply.

Since it is a very simple editorial change, without changing the code, I am directly reinstating the positive review.

Apply trac11856_exponent_overflow.patch trac11856_fix_docs_32bit.patch

comment:21 Changed 7 years ago by SimonKing

  • Dependencies set to #11339

comment:22 Changed 7 years ago by SimonKing

  • Work issues Conflict with #11339 deleted

comment:23 Changed 7 years ago by SimonKing

  • Dependencies #11339 deleted
  • Status changed from positive_review to needs_work
  • Work issues set to Rebase without #11339

I had rebased my patch against #11339, but it turns out that #11339 needs work -- it creates some doctest errors with sage-4.7.2.alpha3-prerelease. So, I guess it would be better to return to the original patch version, which unfortunately is now lost.

comment:24 Changed 7 years ago by SimonKing

  • Status changed from needs_work to positive_review
  • Work issues Rebase without #11339 deleted

Since this ticket fixes a critical bug, I think it would be good to merge it in sage-4.7.2, rather than waiting for 4.7.3. Since #11339 seems to need work, I returned to the original first patch and hope that it is ok to renew Martin's and Alexander's positive review.

Apply trac11856_exponent_overflow.patch trac11856_fix_docs_32bit.patch

Changed 7 years ago by SimonKing

Mimmick Singular's exponent overflow check but still avoids some bugs that Singular provides

comment:25 Changed 7 years ago by SimonKing

  • Dependencies set to #10903

It seems that I should not have rebased my ticket wrt #11339, but wrt #10903 (which in turn has #11339 as a dependency).

Namely, #11339 only works together with #10903.

Solution: Both #11339 and #10903 have a positive review. Hence, it is fine to make #10903 (and thus #11339 by transitivity) a dependency.

Running doctests now, again.

Apply trac11856_exponent_overflow.patch trac11856_fix_docs_32bit.patch

comment:26 Changed 7 years ago by SimonKing

FWIW: The doctests are fine. So, it is justified to keep the positive review of Martin and Alexander.

comment:27 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:28 Changed 4 years ago by jakobkroeker

  • Cc jakobkroeker added
Note: See TracTickets for help on using tickets.