Opened 9 years ago

Last modified 8 years ago

#13609 closed defect

symbolic arithmetic errors — at Version 6

Reported by: llpamies Owned by: burcin
Priority: major Milestone: sage-6.2
Component: symbolics Keywords: pynac segfault
Cc: Merged in:
Authors: Burcin Erocal Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13729, #13736 Stopgaps:

Status badges

Description (last modified by burcin)

Consider the following code:

ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
r1,r2 = var('r1,r2')
expression = -(c1*r2 - c2*r1)/c3
print expression.substitute(r1=z, r2=z)

This produces a TypeError?: unsupported operand parent(s) for '*': 'Finite Field in z of size 2pow8' and 'Rational Field'. I know that 'expression' is not an element of the ring 'poly', but using a PolynomialRing? is the only way I found to achieve symbolic arithmetic on finite fields.

However, the interesting story is that if I replace the expression by

expression = -(r2 - c2*r1)/c3

it work perfectly well, but if instead the expression is

expression = -(c1 + r2 - c2*r1)/c3

then I get a segmentation fault.

To make things a little bit more interesting I can rename r1 and r2 to a and b:

ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
a,b = var('a,b')
expression = -(c1*b - c2*a)/c3
print expression.substitute(a=z, b=z)

Then it works fine, but produces a segmentation fault for,

expression = -(c1 + b - c2*a)/c3

so you can think that it might be a problem with the use of the names r1 and r2. But this is not the case, if I rename the PolynomialRing? variables instead, from c's to x's:

ff.<z> = GF(2**8, 'z')
poly.<x1,x2,x3> = PolynomialRing(ff, 3, 'x')
r1,r2 = var('r1,r2')
expression = -(x1*r2 - x2*r1)/x3
print expression.substitute(r1=z, r2=z)

Then it works again for the first two expressions but produces a segmentation fault for the third too.

Any idea of what is going wrong here?

Apply trac_13609-gf2_content.take2.patch

Change History (7)

comment:1 Changed 9 years ago by llpamies

  • Component changed from PLEASE CHANGE to symbolics
  • Owner changed from tbd to burcin

comment:2 Changed 9 years ago by burcin

I can confirm the segfaults. The following three examples lead to a crash:

ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
r1,r2 = var('r1,r2')
expression = -(c1 + r2 - c2*r1)/c3
expression.substitute(r1=z, r2=z)
<boom>

a,b = var('a,b')
expression = -(c1 + b - c2*a)/c3
expression.substitute(a=z, b=z)
<boom>

poly.<x1,x2,x3> = PolynomialRing(ff, 3, 'x')
r1,r2 = var('r1,r2')
expression = -(x1 + r2 - x2*r1)/x3
expression.substitute(r1=z, r2=z)
<boom>

The fact that this depends on variable names made me think of ordering issues like #9880, but the examples above still lead to a segfault with patches from that ticket. I am now suspecting a coercion problem.

BTW, the backtrace looks like this:

#0  import_submodule (mod=0xe0ea98, subname=0x7fffff8000e0 "sage", 
    fullname=0x7fffff8000d0 "sage.categories.sage") at Python/import.c:2556
#1  0x00007ffff7b06184 in load_next (mod=0xe0ea98, altmod=0x7ffff7da4af0, 
    p_name=<optimized out>, buf=0x7fffff8000d0 "sage.categories.sage", 
    p_buflen=0x7fffff8010e0) at Python/import.c:2415
#2  0x00007ffff7b067d0 in import_module_level (
    name=0xbac1d9 "rings.integer_ring", globals=<optimized out>, 
    fromlist=0xf91890, level=<optimized out>, locals=<optimized out>)
    at Python/import.c:2136
#3  0x00007ffff7b06d9a in PyImport_ImportModuleLevel (
    name=0xbac1d4 "sage.rings.integer_ring", globals=0xfd7390, 
    locals=<optimized out>, fromlist=0xf91890, level=-1)
    at Python/import.c:2188
#4  0x00007ffff7ae53ef in builtin___import__ (self=<optimized out>, 
    args=<optimized out>, kwds=<optimized out>) at Python/bltinmodule.c:49
#5  0x00007ffff7a408d3 in PyObject_Call (func=0x7ffff7fe2dd0, 
    arg=<optimized out>, kw=<optimized out>) at Objects/abstract.c:2529
#6  0x00007ffff7ae6cd7 in PyEval_CallObjectWithKeywords (func=0x7ffff7fe2dd0, 
    arg=0xb07af8, kw=<optimized out>) at Python/ceval.c:3890
#7  0x00007ffff7ae9622 in PyEval_EvalFrameEx (f=<optimized out>, 
    throwflag=<optimized out>) at Python/ceval.c:2333
#8  0x00007ffff7aee7bd in PyEval_EvalCodeEx (co=0xf90eb0, 
    globals=<optimized out>, locals=<optimized out>, args=<optimized out>, 
    argcount=2, kws=0x7ffff7fba068, kwcount=0, defs=0x0, defcount=0, 
    closure=0x0) at Python/ceval.c:3253
#9  0x00007ffff7a6cb5b in function_call (func=0xf970c8, arg=0x4b26488, 
    kw=0x4c7e300) at Objects/funcobject.c:526
#10 0x00007ffff7a408d3 in PyObject_Call (func=0xf970c8, arg=<optimized out>, 
    kw=<optimized out>) at Objects/abstract.c:2529
#11 0x00007ffff7aeb62a in ext_do_call (nk=78800008, na=2, 
    flags=<optimized out>, pp_stack=0x7fffff801610, func=0xf970c8)
    at Python/ceval.c:4334
#12 PyEval_EvalFrameEx (f=<optimized out>, throwflag=<optimized out>)
    at Python/ceval.c:2705
#13 0x00007ffff7aee7bd in PyEval_EvalCodeEx (co=0x13a7430, 
    globals=<optimized out>, locals=<optimized out>, args=<optimized out>, 
    argcount=2, kws=0x0, kwcount=0, defs=0x13b7ae8, defcount=1, closure=0x0)
    at Python/ceval.c:3253
#14 0x00007ffff7a6ca52 in function_call (func=0x13be6e0, arg=0x4b26560, 
    kw=0x0) at Objects/funcobject.c:526
#15 0x00007ffff7a408d3 in PyObject_Call (func=0x13be6e0, arg=<optimized out>, 
    kw=<optimized out>) at Objects/abstract.c:2529
#16 0x00007fffd47c86ba in py_gcd (__pyx_v_n=0x4b10d60, __pyx_v_k=0x4a9b6c0)
    at sage/symbolic/pynac.cpp:7096
#17 0x00007fffd44d4cf4 in GiNaC::gcd(GiNaC::numeric const&, GiNaC::numeric const&) () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#18 0x00007fffd44b2bc9 in GiNaC::add::integer_content() const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#19 0x00007fffd44b2a7c in GiNaC::ex::integer_content() const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#20 0x00007fffd44a29c0 in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#21 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#22 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#23 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#24 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#25 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#26 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#27 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#28 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#29 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#30 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#31 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#32 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#33 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#34 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#35 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#36 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#37 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#38 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#39 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#40 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#41 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#42 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#43 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#44 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#45 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#46 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#47 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#48 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#49 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#50 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#51 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
    () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#52 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#53 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
   from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
<mul::eval(), ex::ex(), ex::construct_from_basic() repeated ad nauseam>

comment:3 Changed 9 years ago by burcin

I opened a ticket on the Pynac issue tracker. I'll come up with a patch soon.

Last edited 9 years ago by burcin (previous) (diff)

comment:4 Changed 9 years ago by burcin

  • Authors set to Burcin Erocal
  • Dependencies set to #13729
  • Keywords pynac segfault added
  • Status changed from new to needs_review

Pynac 0.2.6 contains a fix for this. Updating the spkg is #13729.

comment:5 Changed 9 years ago by jpflori

Would it be possible to give a little more details in the doctests introducing text? like explaining that depending on the name/ordering of the variables, the bug was/ was not triggered, whence the different tests made.

And putting expression or ex everywhere rather than changing the name in the middle?

With this I'll happily give positive review.

Changed 9 years ago by burcin

apply only this patch

comment:6 Changed 9 years ago by burcin

  • Dependencies changed from #13729 to #13729, #13736
  • Description modified (diff)
  • Reviewers set to Jean-Pierre Flori

I uploaded a new patch with some text trac_13609-gf2_content.take2.patch. To demonstrate the content of the expressions involved, I wrapped GiNaC's content() method in #13736. This ticket now depends on the patch there.

Note that multiplying the numerator I give in the doctests by the content gives

sage: -num.content(c1)*num
c1 + z*c2 + z

which changes the original leading coefficient -1 by coercing it to GF(2^8).

This does not happen during normalization, since numeric::div_dyn() is used directly to modify the coefficients. There is a shortcut in that function to do nothing if we are dividing by 1. Perhaps I should back out the current fix in Pynac and change numeric::div_dyn() to disable the shortcut if the characteristic is not 0.

Comments?

Note: See TracTickets for help on using tickets.