Opened 10 years ago
Closed 8 years ago
#12718 closed defect (fixed)
polynomial substitution overflow hell (libsingular bug?)
Reported by:  was  Owned by:  malb 

Priority:  critical  Milestone:  sage6.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: 
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)
Change History (28)
comment:1 Changed 10 years ago by
 Stopgaps set to todo
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
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 10 years ago by
 Status changed from new to needs_review
comment:5 Changed 10 years ago by
I am not sure what I am supposed to do about this stopgap business.
comment:6 Changed 10 years ago by
 Status changed from needs_review to needs_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 Pythoncallable functions that define it.
Changed 10 years ago by
comment:7 Changed 10 years ago by
 Status changed from needs_work to needs_review
comment:8 Changed 10 years ago by
I removed max_degree_per_variable
because it turns out to not work anyway.
comment:9 Changed 10 years ago by
Looks good!
comment:10 Changed 10 years ago by
 Reviewers set to Volker Braun, William Stein
 Status changed from needs_review to positive_review
 Stopgaps todo deleted
comment:11 Changed 10 years ago by
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 10 years ago by
Never mind, the difference is hardly noticable anyway. Your way (with the conditional sig_on()
) seems to be very slightly faster.
comment:13 Changed 10 years ago by
Btw. it's the "standard" way we do it in the singular interface. I think Joel Mohler introduced it ages ago.
comment:14 Changed 10 years ago by
 Status changed from positive_review to needs_work
On 32bit systems:
********************************************************************** File "/Users/buildbot/build/sage/moufang1/moufang_full/build/sage5.0.beta15/devel/sagemain/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/moufang1/moufang_full/build/sage5.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/moufang1/moufang_full/build/sage5.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/moufang1/moufang_full/build/sage5.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/moufang1/moufang_full/build/sage5.0.beta15/devel/sagemain/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/moufang1/moufang_full/build/sage5.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/moufang1/moufang_full/build/sage5.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/moufang1/moufang_full/build/sage5.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). **********************************************************************
comment:15 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:16 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:17 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:18 Changed 8 years ago by
 Branch set to u/malb/trac_12718
 Commit set to a35f3d18c57f087e99419ee47d89f4e170c2d23b
 Keywords sd59 added
 Status changed from needs_work to needs_review
A mere two years later … and I fixed those doctest failures.
New commits:
a35f3d1  catch overflows in f.subs() where f is a libsingular polynomial

comment:19 Changed 8 years ago by
 Commit changed from a35f3d18c57f087e99419ee47d89f4e170c2d23b to 38c07da8745a467c2669ee70adab4e5fbb927876
comment:20 Changed 8 years ago by
fixed segfault.
comment:21 Changed 8 years ago by
anyone up for reviewing this?
comment:22 Changed 8 years ago by
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
 Status changed from needs_review to needs_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
 Commit changed from 38c07da8745a467c2669ee70adab4e5fbb927876 to 3e8a09e700d9a83f84e1c2085818d6aea81b1515
comment:25 Changed 8 years ago by
 Commit changed from 3e8a09e700d9a83f84e1c2085818d6aea81b1515 to 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc
Branch pushed to git repo; I updated commit sha1. New commits:
a35f3d1  catch overflows in f.subs() where f is a libsingular polynomial

4dfd393  Merge branch 'develop' into trac_12718

c9a1ebc  fixed SIGSEGV when calling subs on 0

38c07da  shut up Cython warnings about complicated declarations

5f84119  fixed some doctest failures

18ddc6d  we still need to run subst if self == 0 to allow ring changes

comment:26 Changed 8 years ago by
 Status changed from needs_work to needs_review
Okay, figured out what went wrong:
 the doctest failure Volker posted was missed because I ran my last tests on 32bit not on 64bit, but it only shows on 64bit
 the other doctest failures were introduced in my last  seemingly innocent  fix
I've addressed these and ran doctests on one 64bit and one 32bit system. They passed.
comment:27 Changed 8 years ago by
 Branch changed from u/malb/trac_12718 to 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc
 Resolution set to fixed
 Status changed from needs_review to closed
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.