Opened 11 years ago

Closed 8 years ago

#12718 closed defect (fixed)

polynomial substitution overflow hell (libsingular bug?)

Reported by: William Stein Owned by: Martin Albrecht
Priority: critical Milestone: sage-6.3
Component: commutative algebra Keywords: sd59
Cc: Merged in:
Authors: Martin Albrecht Reviewers: Volker Braun, William Stein
Report Upstream: N/A Work issues:
Branch: 18ddc6d (Commits, GitHub, GitLab) Commit: 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc
Dependencies: Stopgaps:

Status badges

Description

sage: R.<x,y> = QQ[]
sage: n=1000; f = x^n; f.subs(x = x^n)
x^1000000
sage: n=100000; f = x^n; f.subs(x = x^n)
x^1410065408*y^2 

Attachments (1)

trac_12718_singular_overflow.patch (17.2 KB) - added by Martin Albrecht 11 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 11 years ago by William Stein

Stopgaps: todo

comment:2 Changed 11 years ago by Martin Albrecht

Ah, crap, we took care of the actual overflows but missed this one. I'll try to port our fix from __pow__ over this weekend.

comment:3 Changed 11 years ago by William Stein

By the way, this bug was quickly hit by Ben Hutz, who is doing research in arithmetic dynamics, which involves dynamics of *iterating* maps.

comment:4 Changed 11 years ago by Martin Albrecht

Authors: Martin Albrecht
Status: newneeds_review

comment:5 Changed 11 years ago by Martin Albrecht

I am not sure what I am supposed to do about this stopgap business.

comment:6 Changed 11 years ago by William Stein

Status: needs_reviewneeds_work

REFEREE REPORT:

This looks great except for one little thing. Can you give examples to illustrate the max_degree_per_variable parameter in the Python-callable functions that define it.

Changed 11 years ago by Martin Albrecht

comment:7 Changed 11 years ago by Martin Albrecht

Status: needs_workneeds_review

comment:8 Changed 11 years ago by Martin Albrecht

I removed max_degree_per_variable because it turns out to not work anyway.

comment:9 Changed 11 years ago by Volker Braun

Looks good!

comment:10 Changed 11 years ago by Volker Braun

Reviewers: Volker Braun, William Stein
Status: needs_reviewpositive_review
Stopgaps: todo

comment:11 Changed 11 years ago by Jeroen Demeyer

In cdef int singular_polynomial_subst(), did you verify that adding the sig_on() conditions doesn't slow things down? If you need a function call to determine whether to call sig_on(), it's probably faster to always call sig_on().

comment:12 Changed 11 years ago by Jeroen Demeyer

Never mind, the difference is hardly noticable anyway. Your way (with the conditional sig_on()) seems to be very slightly faster.

comment:13 Changed 11 years ago by Martin Albrecht

Btw. it's the "standard" way we do it in the singular interface. I think Joel Mohler introduced it ages ago.

comment:14 Changed 11 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

On 32-bit systems:

**********************************************************************
File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/devel/sage-main/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3154:
    sage: n=1000; f = x^n; f.subs(x = x^n)
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[28]>", line 1, in <module>
        n=Integer(1000); f = x**n; f.subs(x = x**n)###line 3154:
    sage: n=1000; f = x^n; f.subs(x = x^n)
      File "multi_polynomial_libsingular.pyx", line 3240, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.subs (sage/rings/polynomial/multi_polynomial_libsingular.cpp:21411)
        raise OverflowError("Exponent overflow (%d)."%(degree))
    OverflowError: Exponent overflow (1000000).
**********************************************************************
File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/devel/sage-main/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3157:
    sage: n=100000; f = x^n; f.subs(x = x^n)
Expected:
    Traceback (most recent call last):
    ...
    OverflowError: Exponent overflow (10000000000).
Got:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/moufang-1/moufang_full/build/sage-5.0.beta15/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[29]>", line 1, in <module>
        n=Integer(100000); f = x**n; f.subs(x = x**n)###line 3157:
    sage: n=100000; f = x^n; f.subs(x = x^n)
      File "multi_polynomial_libsingular.pyx", line 2347, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.__pow__ (sage/rings/polynomial/multi_polynomial_libsingular.cpp:16619)
        singular_polynomial_pow(&_p, self._poly, exp, _ring)
      File "polynomial.pyx", line 322, in sage.libs.singular.polynomial.singular_polynomial_pow (sage/libs/singular/polynomial.cpp:3976)
      File "singular.pyx", line 667, in sage.libs.singular.singular.overflow_check (sage/libs/singular/singular.cpp:6526)
    OverflowError: Exponent overflow (100000).
**********************************************************************
Last edited 11 years ago by Jeroen Demeyer (previous) (diff)

comment:15 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:16 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:17 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:18 Changed 8 years ago by Martin Albrecht

Branch: u/malb/trac_12718
Commit: a35f3d18c57f087e99419ee47d89f4e170c2d23b
Keywords: sd59 added
Status: needs_workneeds_review

A mere two years later … and I fixed those doctest failures.


New commits:

a35f3d1catch overflows in f.subs() where f is a libsingular polynomial

comment:19 Changed 8 years ago by git

Commit: a35f3d18c57f087e99419ee47d89f4e170c2d23b38c07da8745a467c2669ee70adab4e5fbb927876

Branch pushed to git repo; I updated commit sha1. New commits:

4dfd393Merge branch 'develop' into trac_12718
c9a1ebcfixed SIGSEGV when calling subs on 0
38c07dashut up Cython warnings about complicated declarations

comment:20 Changed 8 years ago by Martin Albrecht

fixed segfault.

comment:21 Changed 8 years ago by Martin Albrecht

anyone up for reviewing this?

comment:22 Changed 8 years ago by Volker Braun

I'm getting a bunch of doctest errors, including

sage -t --long src/sage/rings/polynomial/multi_polynomial_libsingular.pyx
**********************************************************************
File "src/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 3279, in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.subs
Failed example:
    try:
      f.subs(x = x^n)
      print "no overflow"
    except OverflowError:
      print "overflow"
Expected:
    no overflow 
Got:
    x^1000000
    no overflow

but really there is a bunch more. Did you run the tests?

comment:23 Changed 8 years ago by Martin Albrecht

Status: needs_reviewneeds_work

I did and they passed (I thought at least), but I'm now getting these, too. Damn.

comment:24 Changed 8 years ago by git

Commit: 38c07da8745a467c2669ee70adab4e5fbb9278763e8a09e700d9a83f84e1c2085818d6aea81b1515

Branch pushed to git repo; I updated commit sha1. New commits:

5f84119fixed some doctest failures
3e8a09ewe still need to run subst if self == 0 to allow ring changes

comment:25 Changed 8 years ago by git

Commit: 3e8a09e700d9a83f84e1c2085818d6aea81b151518ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc

Branch pushed to git repo; I updated commit sha1. New commits:

a35f3d1catch overflows in f.subs() where f is a libsingular polynomial
4dfd393Merge branch 'develop' into trac_12718
c9a1ebcfixed SIGSEGV when calling subs on 0
38c07dashut up Cython warnings about complicated declarations
5f84119fixed some doctest failures
18ddc6dwe still need to run subst if self == 0 to allow ring changes

comment:26 Changed 8 years ago by Martin Albrecht

Status: needs_workneeds_review

Okay, figured out what went wrong:

  • the doctest failure Volker posted was missed because I ran my last tests on 32-bit not on 64-bit, but it only shows on 64-bit
  • the other doctest failures were introduced in my last - seemingly innocent - fix

I've addressed these and ran doctests on one 64-bit and one 32-bit system. They passed.

comment:27 Changed 8 years ago by Volker Braun

Branch: u/malb/trac_1271818ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc
Resolution: fixed
Status: needs_reviewclosed
Note: See TracTickets for help on using tickets.