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