Opened 11 years ago

Closed 9 years ago

# polynomial substitution overflow hell (libsingular bug?)

Reported by: Owned by: was malb critical sage-6.3 commutative algebra sd59 Martin Albrecht Volker Braun, William Stein N/A 18ddc6d 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc

### 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
```

### comment:1 Changed 11 years ago by was

Stopgaps: → todo

### comment:2 Changed 11 years ago by malb

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 was

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 malb

Authors: → Martin Albrecht new → needs_review

### comment:6 Changed 11 years ago by was

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.

### comment:7 Changed 11 years ago by malb

Status: needs_work → needs_review

### comment:8 Changed 11 years ago by malb

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

Looks good!

### comment:10 Changed 11 years ago by vbraun

Reviewers: → Volker Braun, William Stein needs_review → positive_review todo

### comment:11 Changed 11 years ago by jdemeyer

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 jdemeyer

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 malb

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 jdemeyer

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).
**********************************************************************
```
Version 0, edited 11 years ago by jdemeyer (next)

### comment:15 Changed 9 years ago by jdemeyer

Milestone: sage-5.11 → sage-5.12

### comment:16 Changed 9 years ago by vbraun_spam

Milestone: sage-6.1 → sage-6.2

### comment:17 Changed 9 years ago by vbraun_spam

Milestone: sage-6.2 → sage-6.3

### comment:18 Changed 9 years ago by malb

Branch: → u/malb/trac_12718 → a35f3d18c57f087e99419ee47d89f4e170c2d23b sd59 added 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 git

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

 ​4dfd393 `Merge branch 'develop' into trac_12718` ​c9a1ebc `fixed SIGSEGV when calling subs on 0` ​38c07da `shut up Cython warnings about complicated declarations`

fixed segfault.

### comment:21 Changed 9 years ago by malb

anyone up for reviewing this?

### comment:22 Changed 9 years ago by vbraun

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 malb

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 git

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

 ​5f84119 `fixed some doctest failures` ​3e8a09e `we still need to run subst if self == 0 to allow ring changes`

### comment:25 Changed 9 years ago by git

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 malb

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 vbraun

Branch: u/malb/trac_12718 → 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc → fixed needs_review → closed
Note: See TracTickets for help on using tickets.