Opened 11 years ago
Closed 9 years ago
#12718 closed defect (fixed)
polynomial substitution overflow hell (libsingular bug?)
Reported by: | was | Owned by: | malb |
---|---|---|---|
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: |
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 11 years ago by
Stopgaps: | → todo |
---|
comment:2 Changed 11 years ago by
comment:3 Changed 11 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 11 years ago by
Authors: | → Martin Albrecht |
---|---|
Status: | new → needs_review |
comment:5 Changed 11 years ago by
I am not sure what I am supposed to do about this stopgap business.
comment:6 Changed 11 years ago by
Status: | needs_review → 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 Python-callable functions that define it.
Changed 11 years ago by
Attachment: | trac_12718_singular_overflow.patch added |
---|
comment:7 Changed 11 years ago by
Status: | needs_work → needs_review |
---|
comment:8 Changed 11 years ago by
I removed max_degree_per_variable
because it turns out to not work anyway.
comment:10 Changed 11 years ago by
Reviewers: | → Volker Braun, William Stein |
---|---|
Status: | needs_review → positive_review |
Stopgaps: | todo |
comment:11 Changed 11 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 11 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 11 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 11 years ago by
Status: | positive_review → needs_work |
---|
On moufang (OSX 10.4 ppc32):
********************************************************************** 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). **********************************************************************
comment:15 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:16 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:17 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:18 Changed 9 years ago by
Branch: | → u/malb/trac_12718 |
---|---|
Commit: | → a35f3d18c57f087e99419ee47d89f4e170c2d23b |
Keywords: | sd59 added |
Status: | needs_work → 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 9 years ago by
Commit: | a35f3d18c57f087e99419ee47d89f4e170c2d23b → 38c07da8745a467c2669ee70adab4e5fbb927876 |
---|
comment:22 Changed 9 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 9 years ago by
Status: | needs_review → needs_work |
---|
I did and they passed (I thought at least), but I'm now getting these, too. Damn.
comment:24 Changed 9 years ago by
Commit: | 38c07da8745a467c2669ee70adab4e5fbb927876 → 3e8a09e700d9a83f84e1c2085818d6aea81b1515 |
---|
comment:25 Changed 9 years ago by
Commit: | 3e8a09e700d9a83f84e1c2085818d6aea81b1515 → 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 9 years ago by
Status: | needs_work → needs_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 9 years ago by
Branch: | u/malb/trac_12718 → 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc |
---|---|
Resolution: | → fixed |
Status: | needs_review → 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.