Sage: Ticket #13609: symbolic arithmetic errors
https://trac.sagemath.org/ticket/13609
<p>
Consider the following code:
</p>
<pre class="wiki">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)
</pre><p>
This produces a <a class="missing wiki">TypeError?</a>: 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 <a class="missing wiki">PolynomialRing?</a> is the only way I found to achieve symbolic arithmetic on finite fields.
</p>
<p>
However, the interesting story is that if I replace the expression by
</p>
<pre class="wiki">expression = -(r2 - c2*r1)/c3
</pre><p>
it work perfectly well, but if instead the expression is
</p>
<pre class="wiki">expression = -(c1 + r2 - c2*r1)/c3
</pre><p>
then I get a segmentation fault.
</p>
<p>
To make things a little bit more interesting I can rename r1 and r2 to a and b:
</p>
<pre class="wiki">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)
</pre><p>
Then it works fine, but produces a segmentation fault for,
</p>
<pre class="wiki">expression = -(c1 + b - c2*a)/c3
</pre><p>
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 <a class="missing wiki">PolynomialRing?</a> variables instead, from c's to x's:
</p>
<pre class="wiki">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)
</pre><p>
Then it works again for the first two expressions but produces a segmentation fault for the third too.
</p>
<p>
Any idea of what is going wrong here?
</p>
<p>
Apply <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13609/trac_13609-rebase.patch" title="Attachment 'trac_13609-rebase.patch' in Ticket #13609">trac_13609-rebase.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13609/trac_13609-rebase.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13609
Trac 1.1.6llpamiesTue, 23 Oct 2012 06:32:38 GMTowner, component changed
https://trac.sagemath.org/ticket/13609#comment:1
https://trac.sagemath.org/ticket/13609#comment:1
<ul>
<li><strong>owner</strong>
changed from <em>tbd</em> to <em>burcin</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>symbolics</em>
</li>
</ul>
TicketburcinWed, 07 Nov 2012 15:24:42 GMT
https://trac.sagemath.org/ticket/13609#comment:2
https://trac.sagemath.org/ticket/13609#comment:2
<p>
I can confirm the segfaults. The following three examples lead to a crash:
</p>
<pre class="wiki">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>
</pre><p>
The fact that this depends on variable names made me think of ordering issues like <a class="closed ticket" href="https://trac.sagemath.org/ticket/9880" title="defect: Pynac comparison functions do not provide a SWO (closed: fixed)">#9880</a>, but the examples above still lead to a segfault with patches from that ticket. I am now suspecting a coercion problem.
</p>
<p>
BTW, the backtrace looks like this:
</p>
<pre class="wiki">#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>
</pre>
TicketburcinThu, 08 Nov 2012 14:57:08 GMT
https://trac.sagemath.org/ticket/13609#comment:3
https://trac.sagemath.org/ticket/13609#comment:3
<p>
I opened <a class="ext-link" href="http://hg.pynac.org/pynac/issue/12"><span class="icon"></span>a ticket on the Pynac issue tracker</a>. I'll come up with a patch soon.
</p>
TicketburcinTue, 20 Nov 2012 15:51:58 GMTstatus changed; keywords, dependencies, author set
https://trac.sagemath.org/ticket/13609#comment:4
https://trac.sagemath.org/ticket/13609#comment:4
<ul>
<li><strong>keywords</strong>
<em>pynac</em> <em>segfault</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#13729</em>
</li>
<li><strong>author</strong>
set to <em>Burcin Erocal</em>
</li>
</ul>
<p>
Pynac 0.2.6 contains a fix for this. Updating the spkg is <a class="closed ticket" href="https://trac.sagemath.org/ticket/13729" title="defect: Update pynac to 0.2.6 (closed: fixed)">#13729</a>.
</p>
TicketjpfloriWed, 21 Nov 2012 12:34:00 GMT
https://trac.sagemath.org/ticket/13609#comment:5
https://trac.sagemath.org/ticket/13609#comment:5
<p>
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.
</p>
<p>
And putting expression or ex everywhere rather than changing the name in the middle?
</p>
<p>
With this I'll happily give positive review.
</p>
TicketburcinWed, 21 Nov 2012 15:39:37 GMTattachment set
https://trac.sagemath.org/ticket/13609
https://trac.sagemath.org/ticket/13609
<ul>
<li><strong>attachment</strong>
set to <em>trac_13609-gf2_content.take2.patch</em>
</li>
</ul>
<p>
apply only this patch
</p>
TicketburcinWed, 21 Nov 2012 15:54:50 GMTdependencies, description changed; reviewer set
https://trac.sagemath.org/ticket/13609#comment:6
https://trac.sagemath.org/ticket/13609#comment:6
<ul>
<li><strong>reviewer</strong>
set to <em>Jean-Pierre Flori</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#13729</em> to <em>#13729, #13736</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13609?action=diff&version=6">diff</a>)
</li>
</ul>
<p>
I uploaded a new patch with some text <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13609/trac_13609-gf2_content.take2.patch" title="Attachment 'trac_13609-gf2_content.take2.patch' in Ticket #13609">trac_13609-gf2_content.take2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13609/trac_13609-gf2_content.take2.patch" title="Download"></a>. To demonstrate the content of the expressions involved, I wrapped GiNaC's <code>content()</code> method in <a class="closed ticket" href="https://trac.sagemath.org/ticket/13736" title="enhancement: add content method to symbolic expressions (closed: fixed)">#13736</a>. This ticket now depends on the patch there.
</p>
<p>
Note that multiplying the numerator I give in the doctests by the content
gives
</p>
<pre class="wiki">sage: -num.content(c1)*num
c1 + z*c2 + z
</pre><p>
which changes the original leading coefficient <code>-1</code> by coercing it to <code>GF(2^8)</code>.
</p>
<p>
This does not happen during normalization, since <code>numeric::div_dyn()</code> is used
directly to modify the coefficients. There is a shortcut in that function to
do nothing if we are dividing by <code>1</code>. Perhaps I should back out the current
fix in Pynac and change <code>numeric::div_dyn()</code> to disable the shortcut if the
characteristic is not 0.
</p>
<p>
Comments?
</p>
TicketvbraunThu, 09 May 2013 09:54:16 GMT
https://trac.sagemath.org/ticket/13609#comment:7
https://trac.sagemath.org/ticket/13609#comment:7
<p>
Fuzz 2 on top of sage-5.10.beta2, so needs to be rebased.
</p>
TicketkcrismanTue, 18 Jun 2013 19:47:50 GMTattachment set
https://trac.sagemath.org/ticket/13609
https://trac.sagemath.org/ticket/13609
<ul>
<li><strong>attachment</strong>
set to <em>trac_13609-rebase.patch</em>
</li>
</ul>
<p>
Apply only this
</p>
TicketkcrismanTue, 18 Jun 2013 19:48:21 GMTdescription changed
https://trac.sagemath.org/ticket/13609#comment:8
https://trac.sagemath.org/ticket/13609#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13609?action=diff&version=8">diff</a>)
</li>
</ul>
TicketkcrismanTue, 18 Jun 2013 19:53:31 GMT
https://trac.sagemath.org/ticket/13609#comment:9
https://trac.sagemath.org/ticket/13609#comment:9
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I think it is reasonable to have different behavior outside char 0.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/13609#comment:10
https://trac.sagemath.org/ticket/13609#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/13609#comment:11
https://trac.sagemath.org/ticket/13609#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketmmezzarobbaFri, 14 Mar 2014 13:39:42 GMTcommit, branch set
https://trac.sagemath.org/ticket/13609#comment:12
https://trac.sagemath.org/ticket/13609#comment:12
<ul>
<li><strong>commit</strong>
set to <em>e0d15a9bf67e292d23ff306e2a8e632a280debea</em>
</li>
<li><strong>branch</strong>
set to <em>u/mmezzarobba/ticket/13609</em>
</li>
</ul>
<p>
The fix has been in Sage's version of Pynac for one year. The patch attached to this ticket (which just adds new tests) applies cleanly to sage-6.2.beta4, and the new tests pass. Is there any reason this ticket still needs review?
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e0d15a9bf67e292d23ff306e2a8e632a280debea"><span class="icon"></span>e0d15a9</a></td><td><code>Trac 13609: fix symbolic expression auto evaluation when content is in GF(2^k)</code>
</td></tr></table>
TicketjpfloriFri, 14 Mar 2014 13:45:28 GMT
https://trac.sagemath.org/ticket/13609#comment:13
https://trac.sagemath.org/ticket/13609#comment:13
<p>
I don't really remember, but if you feel happy with the changes let's merge this.
</p>
TicketmmezzarobbaFri, 14 Mar 2014 13:58:35 GMTstatus changed
https://trac.sagemath.org/ticket/13609#comment:14
https://trac.sagemath.org/ticket/13609#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketkcrismanFri, 14 Mar 2014 14:06:12 GMT
https://trac.sagemath.org/ticket/13609#comment:15
https://trac.sagemath.org/ticket/13609#comment:15
<p>
If there is no mathematical problem it's okay; I think that Burcin's point was that sometimes plus and minus one can replace each other with this code sometimes in characteristic two. Which is ... true, they can. It just doesn't "look" the same. Or at least I think that was the point of his comment and doctest along those lines?
</p>
TicketmmezzarobbaFri, 14 Mar 2014 14:38:58 GMT
https://trac.sagemath.org/ticket/13609#comment:16
https://trac.sagemath.org/ticket/13609#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13609#comment:15" title="Comment 15">kcrisman</a>:
</p>
<blockquote class="citation">
<p>
If there is no mathematical problem it's okay; I think that Burcin's point was that sometimes plus and minus one can replace each other with this code sometimes in characteristic two. Which is ... true, they can. It just doesn't "look" the same. Or at least I think that was the point of his comment and doctest along those lines?
</p>
</blockquote>
<p>
In any case, the patch in this ticket only documents the currently implemented behaviour. I'd say any changes to address the behaviour noted in Burcin's comment belong in another ticket.
</p>
TicketvbraunFri, 21 Mar 2014 17:47:41 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/13609#comment:17
https://trac.sagemath.org/ticket/13609#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/mmezzarobba/ticket/13609</em> to <em>e0d15a9bf67e292d23ff306e2a8e632a280debea</em>
</li>
</ul>
Ticket