Opened 19 months ago

Closed 17 months ago

Last modified 17 months ago

#28489 closed defect (fixed)

py3 + OS X: symbolic/expression.pyx

Reported by: jhpalmieri Owned by:
Priority: major Milestone: sage-9.0
Component: python3 Keywords: random_fail
Cc: vbraun Merged in:
Authors: Frédéric Chapoton Reviewers: Volker Braun
Report Upstream: Reported upstream. No feedback yet. Work issues:
Branch: fbffb36 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

On OS X, I get intermittent failures with symbolic/expression.pyx:

sage -t src/sage/symbolic/expression.pyx
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 7122, in sage.symbolic.expression.Expression.gcd
Failed example:
    gcd(alg + alg*x, x^2 - 1)
Exception raised:
    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/arith/misc.py", line 1771, in gcd
        return m(b, **kwargs)
      File "sage/symbolic/expression.pyx", line 7169, in sage.symbolic.expression.Expression.gcd (build/cythonized/sage/symbolic/expression.cpp:40616)
        cdef GEx x = g_gcd(self._gobj, r._gobj)
      File "sage/structure/element.pyx", line 1236, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10816)
        return coercion_model.bin_op(left, right, add)
      File "sage/structure/coerce.pyx", line 1207, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10898)
        raise bin_op_exception(op, x, y)
    TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in I with defining polynomial x^2 + 1 with I = 1*I'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.symbolic.expression.Expression.gcd[13]>", line 1, in <module>
        gcd(alg + alg*x, x**Integer(2) - Integer(1))
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/arith/misc.py", line 1773, in gcd
        return m(py_scalar_to_element(b), **kwargs)
      File "sage/symbolic/expression.pyx", line 7169, in sage.symbolic.expression.Expression.gcd (build/cythonized/sage/symbolic/expression.cpp:40616)
        cdef GEx x = g_gcd(self._gobj, r._gobj)
      File "sage/structure/element.pyx", line 1236, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10816)
        return coercion_model.bin_op(left, right, add)
      File "sage/structure/coerce.pyx", line 1207, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10898)
        raise bin_op_exception(op, x, y)
    TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in I with defining polynomial x^2 + 1 with I = 1*I'
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 7124, in sage.symbolic.expression.Expression.gcd
Failed example:
    gcd(alg - alg*x, x^2 - 1)
Exception raised:
    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/arith/misc.py", line 1771, in gcd
        return m(b, **kwargs)
      File "sage/symbolic/expression.pyx", line 7169, in sage.symbolic.expression.Expression.gcd (build/cythonized/sage/symbolic/expression.cpp:40616)
        cdef GEx x = g_gcd(self._gobj, r._gobj)
      File "sage/structure/element.pyx", line 1236, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10816)
        return coercion_model.bin_op(left, right, add)
      File "sage/structure/coerce.pyx", line 1207, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10898)
        raise bin_op_exception(op, x, y)
    TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in I with defining polynomial x^2 + 1 with I = 1*I'

    During handling of the above exception, another exception occurred:

    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.symbolic.expression.Expression.gcd[14]>", line 1, in <module>
        gcd(alg - alg*x, x**Integer(2) - Integer(1))
      File "/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python3.7/site-packages/sage/arith/misc.py", line 1773, in gcd
        return m(py_scalar_to_element(b), **kwargs)
      File "sage/symbolic/expression.pyx", line 7169, in sage.symbolic.expression.Expression.gcd (build/cythonized/sage/symbolic/expression.cpp:40616)
        cdef GEx x = g_gcd(self._gobj, r._gobj)
      File "sage/structure/element.pyx", line 1236, in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10816)
        return coercion_model.bin_op(left, right, add)
      File "sage/structure/coerce.pyx", line 1207, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10898)
        raise bin_op_exception(op, x, y)
    TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in I with defining polynomial x^2 + 1 with I = 1*I'
**********************************************************************
1 item had failures:
   2 of  29 in sage.symbolic.expression.Expression.gcd
    [2848 tests, 2 failures, 24.89 s]
----------------------------------------------------------------------
sage -t src/sage/symbolic/expression.pyx  # 2 doctests failed
----------------------------------------------------------------------

I get these about a third of the time.

Change History (12)

comment:1 Changed 19 months ago by jhpalmieri

I can also get the error while running Sage, using the commands

sage: var('x,y')
(x, y)
sage: alg = SR(QQbar(sqrt(2) + I*sqrt(3)))
sage: gcd(alg + alg*x, x^2 - 1)
x + 1

This also happens about a third of the times I run Sage. In a given Sage session, it either always works or always fails, but if I restart Sage, the behavior can change.

comment:2 Changed 19 months ago by gh-mwageringel

I can reproduce this on OS X, but not on CentOS.

comment:3 Changed 19 months ago by klee

The error can be reproduced only by

alg = QQbar(I); gcd(x, alg)

It seem that pynac intermittently triggers the following not-allowed operation

sage: N.<i> = NumberField(x^2+1)
sage: QQbar(I).parent().base()(1) + i
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-fd4130c2c6dc> in <module>()
----> 1 QQbar(I).parent().base()(Integer(1)) + i

/Users/kwankyu/GitHub/sage-dev/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__add__ (build/cythonized/sage/structure/element.c:10816)()
   1234         # Left and right are Sage elements => use coercion model
   1235         if BOTH_ARE_ELEMENT(cl):
-> 1236             return coercion_model.bin_op(left, right, add)
   1237 
   1238         cdef long value

/Users/kwankyu/GitHub/sage-dev/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10898)()
   1205         # We should really include the underlying error.
   1206         # This causes so much headache.
-> 1207         raise bin_op_exception(op, x, y)
   1208 
   1209     cpdef canonical_coercion(self, x, y):

TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in i with defining polynomial x^2 + 1'

pynac experts should help.

comment:4 Changed 19 months ago by jhpalmieri

  • Report Upstream changed from N/A to Reported upstream. No feedback yet.

comment:5 Changed 18 months ago by gh-mwageringel

sage: gcd(x, QQbar(I))

In Pynac, the above computation raises the error in the line

        map.insert(std::make_pair(e, index));

of replace_with_symbol invoked from num2canonical, where the expression e is I and the insert method is from std::unordered_map. At this point, using Log(map);, the map looks like:

    {4}
    1 => 4
    0 => 3
    x => 2
    symbol0 => 1

The insert function will need to compute the hash of the expression e (which succeeds) and, upon hash collisions, will need to perform equality tests with elements that are already stored in the map. I do not know where exactly this equality test is implemented, but this must be the step that fails. This explains the randomness in the bug, as the hash values depend on the session, so a collision for I might or might not occur. Additionally, this might depend on the implementation of the C++ standard library – though in principle this bug can occur on every platform, even with Python 2.

The equality test seems to check whether the difference of two elements is zero, resulting in the computation of 1 + (-I). Here, 1 is of type AlgebraicReal and -I is a NumberFieldElement_quadratic.


I see two potential ways out:

One option is to always raise a NotImplementedError when attempting to compute the GCD of symbolic polynomials. As per the documentation, it does not reliably give correct results anyway:

        Embedded Sage objects of all kinds get basic support. Note that
        full algebraic GCD is not implemented yet::

            ...
            sage: sqrt2 = SR(QQbar(sqrt(2)))
            sage: gcd(sqrt2 + x, x^2 - 2)    # known bug
            1

The other option is to make the following addition work. And by my understanding of the coercion framework, it actually should work, as both arguments coerce to CLF, since the quadratic number field N comes with a complex embedding:

sage: N, i_neg, emb = QQbar(-I).as_number_field_element()
sage: AA(1) + i_neg  # this should work
...
TypeError: unsupported operand parent(s) for +: 'Algebraic Real Field' and 'Number Field in I with defining polynomial x^2 + 1 with I = 1*I'
sage: N.coerce_embedding()
Generic morphism:
  From: Number Field in I with defining polynomial x^2 + 1 with I = 1*I
  To:   Complex Lazy Field
  Defn: I -> 1*I
sage: CLF.has_coerce_map_from(AA), CLF.has_coerce_map_from(N)
(True, True)
sage: CLF(AA(1)) + CLF(i_neg)
1 - 1*I

Making this addition work could be quite useful in general. Any suggestions how to solve this?

Last edited 18 months ago by gh-mwageringel (previous) (diff)

comment:6 Changed 17 months ago by vbraun

  • Cc vbraun added
  • Keywords random_fail added

comment:7 Changed 17 months ago by vbraun

This seems all pretty complicated. Can we at least for now just add a # known bug? According to the discussion here its not a new bug, we just are now hitting an old one.

comment:8 Changed 17 months ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to public/ticket/28489
  • Commit set to fbffb36597e4fef6332ca1136381af3feddbc530
  • Status changed from new to needs_review

New commits:

fbffb36trac 28489 known bug in gcd for python3 on osX

comment:9 Changed 17 months ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

comment:10 Changed 17 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

comment:11 Changed 17 months ago by vbraun

  • Branch changed from public/ticket/28489 to fbffb36597e4fef6332ca1136381af3feddbc530
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 17 months ago by klee

  • Commit fbffb36597e4fef6332ca1136381af3feddbc530 deleted

I feel somewhat guilty about the solution here. Hence I created #28827 to track the issue elsewhere.

Note: See TracTickets for help on using tickets.