Opened 10 years ago

Closed 7 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:

Status badges

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)

trac_12718_singular_overflow.patch (17.2 KB) - added by malb 10 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 10 years ago by was

  • Stopgaps set to todo

comment:2 Changed 10 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 10 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 10 years ago by malb

  • Authors set to Martin Albrecht
  • Status changed from new to needs_review

comment:5 Changed 10 years ago by malb

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

comment:6 Changed 10 years ago by was

  • 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 Python-callable functions that define it.

Changed 10 years ago by malb

comment:7 Changed 9 years ago by malb

  • Status changed from needs_work to needs_review

comment:8 Changed 9 years ago by malb

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

comment:9 Changed 9 years ago by vbraun

Looks good!

comment:10 Changed 9 years ago by vbraun

  • Reviewers set to Volker Braun, William Stein
  • Status changed from needs_review to positive_review
  • Stopgaps todo deleted

comment:11 Changed 9 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 9 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 9 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 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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).
**********************************************************************
Last edited 9 years ago by jdemeyer (previous) (diff)

comment:15 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:16 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 7 years ago by malb

  • 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:

a35f3d1catch overflows in f.subs() where f is a libsingular polynomial

comment:19 Changed 7 years ago by git

  • Commit changed from a35f3d18c57f087e99419ee47d89f4e170c2d23b to 38c07da8745a467c2669ee70adab4e5fbb927876

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

4dfd393Merge branch 'develop' into trac_12718
c9a1ebcfixed SIGSEGV when calling subs on 0
38c07dashut up Cython warnings about complicated declarations

comment:20 Changed 7 years ago by malb

fixed segfault.

comment:21 Changed 7 years ago by malb

anyone up for reviewing this?

comment:22 Changed 7 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 7 years ago by malb

  • 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 7 years ago by git

  • Commit changed from 38c07da8745a467c2669ee70adab4e5fbb927876 to 3e8a09e700d9a83f84e1c2085818d6aea81b1515

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

5f84119fixed some doctest failures
3e8a09ewe still need to run subst if self == 0 to allow ring changes

comment:25 Changed 7 years ago by git

  • Commit changed from 3e8a09e700d9a83f84e1c2085818d6aea81b1515 to 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc

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

a35f3d1catch overflows in f.subs() where f is a libsingular polynomial
4dfd393Merge branch 'develop' into trac_12718
c9a1ebcfixed SIGSEGV when calling subs on 0
38c07dashut up Cython warnings about complicated declarations
5f84119fixed some doctest failures
18ddc6dwe still need to run subst if self == 0 to allow ring changes

comment:26 Changed 7 years ago by malb

  • 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 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 7 years ago by vbraun

  • Branch changed from u/malb/trac_12718 to 18ddc6dec77d39d764dcaa9fbdbe91adf02bfbbc
  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.