polynomial substitution overflow hell (libsingular bug?)

[was]

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 

[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.

[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.

[malb]

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

[was]

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.

[malb]

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

[vbraun]

Looks good!

[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().

[jdemeyer]

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

[malb]

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

[jdemeyer]

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).
**********************************************************************

[malb]

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

[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

[malb]

fixed segfault.

[malb]

anyone up for reviewing this?

[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?

[malb]

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

[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

[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

[malb]

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.