Opened 10 years ago
Closed 9 years ago
#14888 closed enhancement (fixed)
Make FiniteField_pari_ffelt the default for generic finite fields
Reported by: | pbruin | Owned by: | cpernet |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | finite rings | Keywords: | FiniteField performance |
Cc: | Merged in: | sage-5.13.beta0 | |
Authors: | Peter Bruin, Jeroen Demeyer | Reviewers: | Jean-Pierre Flori, Jeroen Demeyer, Peter Bruin |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12142, #15124, #15125 | Stopgaps: |
Description (last modified by )
Ticket #12142 implements an interface to PARI's t_FFELT type for finite fields, which is much faster than the one currently used by Sage, in which finite field elements are PARI objects like Mod(Mod(1, 3)*a, Mod(1, 3)*a^17 + Mod(2, 3)*a + Mod(1, 3))
. The attached patch makes the new implementation the default for those finite fields that currently use the slow PARI implementation, namely those of cardinality pn with p > 2 prime, n > 1 and pn > 216.
The actual switch is just a trivial change in the FiniteField
constructor. The only other real addition is construction of Integer
from t_FFELT
; the rest of the patch fixes doctests. Almost all fixes are for doctests that assumed FiniteField_elt_pari
to be the default. One somewhat notable point is that certain finite elements now compare differently (see the changed doctest in polynomial_zz_pex.py
). This is because gcmp_sage
(in sage/libs/pari/misc.h
) compares all non-real PARI types via their string representations. With the new FiniteFieldElement_pari_ffelt
, string comparison gives the same result as lexicographic comparison of polynomials expressing finite field elements in terms of the chosen generator, which is nice.
Apply:
Attachments (3)
Change History (47)
Changed 10 years ago by
Attachment: | trac_14888-switch_to_pari_ffelt.patch added |
---|
comment:1 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:2 Changed 10 years ago by
Reviewers: | → Jean-Pierre Flori |
---|---|
Status: | needs_review → positive_review |
Looks good and works fine for what I tried, good work Peter!
comment:3 Changed 10 years ago by
comment:4 Changed 10 years ago by
There shouldn't be any problems with pickling, see the comment I just made at #12142.
comment:5 Changed 9 years ago by
Status: | positive_review → needs_work |
---|
Doctest failures on 32-bit systems:
sage -t --long devel/sage/sage/graphs/generic_graph.py ********************************************************************** File "devel/sage/sage/graphs/generic_graph.py", line 14898, in sage.graphs.generic_graph.GenericGraph.plot Failed example: H = S.hecke_matrix(2) Exception raised: Traceback (most recent call last): File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run self.execute(example, compiled, test.globs) File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute exec compiled in globs File "<doctest sage.graphs.generic_graph.GenericGraph.plot[78]>", line 1, in <module> H = S.hecke_matrix(Integer(2)) File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/modular/ssmod/ssmod.py", line 1042, in hecke_matrix SS, II = self.supersingular_points() File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/modular/ssmod/ssmod.py", line 906, in supersingular_points neighbors = Phi_polys(2,X,ss_points[pos]).roots() File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/modular/ssmod/ssmod.py", line 206, in Phi_polys return x.parent()([j_pow[3] - 162000*j_pow[2] + 8748000000*j_pow[1] - File "element.pyx", line 1701, in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:14531) File "coerce.pyx", line 803, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:7330) File "coerce.pyx", line 917, in sage.structure.coerce.CoercionModel_cache_maps.canonical_coercion (sage/structure/coerce.c:8529) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757) File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_pari_ffelt.py", line 501, in _element_constructor_ return self.element_class(self, x) File "element_pari_ffelt.pyx", line 145, in sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt.__init__ (sage/rings/finite_rings/element_pari_ffelt.c:2975) File "element_pari_ffelt.pyx", line 206, in sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt.construct_from (sage/rings/finite_rings/element_pari_ffelt.c:3341) OverflowError: Python int too large to convert to C long **********************************************************************
(the same error occurs in other places)
sage -t --long devel/sage/sage/groups/generic.py ********************************************************************** File "devel/sage/sage/groups/generic.py", line 422, in sage.groups.generic.bsgs Failed example: P=E.lift_x(a); P Expected: (a : 9*a^4 + 22*a^3 + 23*a^2 + 30 : 1) Got: (a : 28*a^4 + 15*a^3 + 14*a^2 + 7 : 1) ********************************************************************** File "devel/sage/sage/groups/generic.py", line 851, in sage.groups.generic.discrete_log_lambda Failed example: P=E.lift_x(a); P Expected: (a : 28*a^4 + 15*a^3 + 14*a^2 + 7 : 1) Got: (a : 9*a^4 + 22*a^3 + 23*a^2 + 30 : 1) **********************************************************************
(due to a different square root being returned)
comment:6 Changed 9 years ago by
The first problem is in the following code:
elif isinstance(x, int) or isinstance(x, long): g = (<pari_gen>self._parent._gen_pari).g sig_on() x_GEN = stoi(x) self.construct(INT_to_FFELT(g, x_GEN))
The Python long
type doesn't convert to a C long
(confusingly, a C long
corresponds to a Python int
).
To see the problem on 64 bits (let this inspire a doctest):
sage: GF(7^20, 'a')(long(2^63)) --------------------------------------------------------------------------- OverflowError Traceback (most recent call last) <ipython-input-18-d85771ca8953> in <module>() ----> 1 GF(Integer(7)**Integer(20), 'a')(long(Integer(2)**Integer(63))) /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)() /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856)() /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757)() /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_pari_ffelt.pyc in _element_constructor_(self, x) 499 return x 500 else: --> 501 return self.element_class(self, x) 502 503 def _coerce_map_from_(self, R): /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_pari_ffelt.so in sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt.__init__ (sage/rings/finite_rings/element_pari_ffelt.c:2975)() /mazur/release/merger/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_pari_ffelt.so in sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt.construct_from (sage/rings/finite_rings/element_pari_ffelt.c:3341)() OverflowError: Python int too large to convert to C long
comment:8 Changed 9 years ago by
There are more serious issues with element_pari_ffelt.pyx
. For example, it really requires sig_on()
to be the sig_on()
from libs/pari/gen.pyx
. So I feel like this ticket isn't quite ready yet.
comment:9 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Work issues: | → PARI sig_on() |
comment:10 Changed 9 years ago by
Dependencies: | #12142 → #12142, #15124, #15125 |
---|---|
Description: | modified (diff) |
Milestone: | sage-5.12 → sage-pending |
Changed 9 years ago by
Attachment: | 14888_fix_32bit.patch added |
---|
comment:11 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Milestone: | sage-pending → sage-5.13 |
Status: | needs_work → needs_review |
comment:12 Changed 9 years ago by
Reviewers: | Jean-Pierre Flori → Jean-Pierre Flori, Jeroen Demeyer |
---|---|
Work issues: | PARI sig_on() |
comment:13 Changed 9 years ago by
Somebody should review 14888_fix_32bit.patch which fixes doctests on 32-bit systems.
comment:14 Changed 9 years ago by
Looks good and still passes tests on my 64-bit system. I would give 14888_fix_32bit.patch a positive review except for the fact that the main change in it is specifically for 32-bit systems; at least somebody with a 32-bit system should verify that specific doctest.
comment:15 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
I assure you that doctests pass on 32-bit.
comment:16 Changed 9 years ago by
This happens sometimes:
********************************************************************** File "devel/sage/sage/schemes/plane_conics/con_finite_field.py", line 110, in sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.? Failed example: C.has_rational_point(point = True) # output is random Exception raised: Traceback (most recent call last): File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run self.execute(example, compiled, test.globs) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute exec compiled in globs File "<doctest sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.?[9]>", line 1, in <module> C.has_rational_point(point = True) # output is random File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/plane_conics/con_finite_field.py", line 132, in has_rational_point s, pt = self.has_singular_point(point = True) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/plane_conics/con_field.py", line 595, in has_singular_point return True, self.point(Sequence(D.right_kernel().gen())) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/plane_conics/con_field.py", line 886, in point p = ProjectiveCurve_generic.point(self, v, check=check) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/generic/scheme.py", line 370, in point return self.point_homset() (v, check=check) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/generic/homset.py", line 263, in __call__ return Set_generic.__call__(self, *args, **kwds) File "parent.pyx", line 1011, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8392) File "coerce_maps.pyx", line 427, in sage.structure.coerce_maps.ListMorphism._call_with_args (sage/structure/coerce_maps.c:8035) File "coerce_maps.pyx", line 100, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4278) File "coerce_maps.pyx", line 90, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (sage/structure/coerce_maps.c:4089) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/generic/homset.py", line 455, in _element_constructor_ return self.codomain()._point(self, v, **kwds) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/generic/algebraic_scheme.py", line 583, in _point return self.__A._point(*args, **kwds) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_space.py", line 835, in _point return SchemeMorphism_point_projective_finite_field(*args, **kwds) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_point.py", line 764, in __init__ X.extended_codomain()._check_satisfies_equations(v) File "/scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/generic/algebraic_scheme.py", line 967, in _check_satisfies_equations raise TypeError, "Coordinates %s do not define a point on %s"%(coords,self) TypeError: Coordinates [0, 0, 1] do not define a point on Projective Conic Curve over Finite Field in a of size 7^20 defined by x^2 + (a)*y^2 + 2*z^2 **********************************************************************
Note the code path in the traceback showing that Sage thinks the conic is singular.
comment:17 Changed 9 years ago by
Adding extra doctests shows
sage -t devel/sage/sage/schemes/plane_conics/con_finite_field.py ********************************************************************** File "devel/sage/sage/schemes/plane_conics/con_finite_field.py", line 110, in sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.? Failed example: C._coefficients Expected: [1, 0, 0, a, 0, 2] Got: [1, 0, 0, a, 0, 0] ********************************************************************** File "devel/sage/sage/schemes/plane_conics/con_finite_field.py", line 112, in sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.? Failed example: D = C.symmetric_matrix(); D Expected: [1 0 0] [0 a 0] [0 0 2] Got: [1 0 0] [0 a 0] [0 0 0] **********************************************************************
comment:18 Changed 9 years ago by
Status: | positive_review → needs_work |
---|
Sorry, this one seems to be hard to debug. And it doesn't help that Singular is involved too because of the defining polynomial.
comment:19 Changed 9 years ago by
Note that I'm not even sure that this patch is what actually causes this...
comment:20 follow-up: 21 Changed 9 years ago by
Hmm, this is annoying. How often does it occur? I just ran doctests on this file several dozens of times and did not get any failures. (System: x86_64 with 5.11.beta3 and this patch applied, and several others which probably shouldn't influence this.)
Do I understand correctly that there are no failures in the doctest checking that the equation is x^2 + (a)*y^2 + 2*z^2
? If so, then the problem can hardly anywhere else than in the initialisation of C._coefficients
, i.e. (probably) when converting the coefficient of z^2
from Singular to PARI.
I did adapt the conversion function (formerly si2sa_GFqPari
, now si2sa_GFq_generic
) in #12142; the changes seem harmless, but this function does look like a possible culprit to me.
comment:21 Changed 9 years ago by
Replying to pbruin:
Hmm, this is annoying. How often does it occur? I just ran doctests on this file several dozens of times and did not get any failures.
That might not be enough times. Try a few hundred or 1000 times.
Do I understand correctly that there are no failures in the doctest checking that the equation is
x^2 + (a)*y^2 + 2*z^2
? If so, then the problem can hardly anywhere else than in the initialisation ofC._coefficients
Exactly.
The first thing I want to do now is to make sure that it is really this ticket which causes the bug.
comment:22 follow-up: 23 Changed 9 years ago by
comment:23 Changed 9 years ago by
comment:24 follow-up: 26 Changed 9 years ago by
I tracked down the problem to this line in devel/sage/sage/libs/singular/singular.pyx
:
ret = ret + c
where ret is a pari_ffelt
element equal to zero, c
is the C long
equal to 2. The result is 0, while it should be 2.
comment:26 follow-up: 27 Changed 9 years ago by
Replying to jdemeyer:
I tracked down the problem to this line in
devel/sage/sage/libs/singular/singular.pyx
:ret = ret + cwhere ret is a
pari_ffelt
element equal to zero,c
is the Clong
equal to 2. The result is 0, while it should be 2.
I wondered about the same line yesterday evening when I was looking at the surrounding function, but thought that it hardly looked like something that could fail with some small probability. Does this line always give the wrong result (and for some reason just isn't called most of the time)?
I noticed that c is defined by cdef int c
(i.e. C int, not Python int), but is later used as a long; is that something to be suspicious about?
If not, then (since c
is wrapped into a Python int
before being added to ret
) it must be the conversion from Python int
to pari_ffelt
that is causing the problem, but in that case it is strange that it only fails here.
comment:27 follow-up: 28 Changed 9 years ago by
Replying to pbruin:
Replying to jdemeyer:
I tracked down the problem to this line in
devel/sage/sage/libs/singular/singular.pyx
:ret = ret + cwhere ret is a
pari_ffelt
element equal to zero,c
is the Clong
equal to 2. The result is 0, while it should be 2.I wondered about the same line yesterday evening when I was looking at the surrounding function, but thought that it hardly looked like something that could fail with some small probability.
Does this line always give the wrong result (and for some reason just isn't called most of the time)?
No, it rarely gives the wrong result.
I noticed that c is defined by
cdef int c
(i.e. C int, not Python int), but is later used as a long; is that something to be suspicious about?
It's not the cleanest coding (c = <int>napGetCoeff(z)
would be better), but I don't see how that could make a difference, especially since this doesn't seem to be a case of overflow.
it must be the conversion from Python
int
topari_ffelt
that is causing the problem
I also guess that this is the problem.
comment:28 Changed 9 years ago by
Replying to jdemeyer:
it must be the conversion from Python
int
topari_ffelt
that is causing the problemI also guess that this is the problem.
In the line ret = ret + c
, could you replace c
by base(c)
to do the coercion explicitly, just to make sure it isn't some quirk in the coercion system? Or insert a line verifying that c == base(c)
to test directly whether it is the conversion that is at fault?
comment:29 Changed 9 years ago by
The annoying thing is that this error is damned hard to reproduce. Sometimes adding debugging code makes the error go away. So as long as we haven't found the root of the problem, we're just guessing.
comment:30 follow-ups: 31 35 Changed 9 years ago by
Here is one more guess: in sage/rings/finite_rings/element_pari_ffelt.pyx
the Python int x
is first converted into a PARI t_INT as follows (lines 209-210):
pari_catch_sig_on() x_GEN = (<pari_gen>pari(x)).g
The order of these two lines should be interchanged.
Before #15125, the second line was x_GEN = stoi(x)
; here pari_catch_sig_on()
must be called first since we call the un-wrapped PARI function. However, now we call pari(x)
, which does its own pari_catch_sig_on()...pari_catch_sig_off()
. As we know, the current error-handling code is non-reentrant. I don't see exactly how this could cause our bug, but maybe my imagination is too limited.
There is a similar mistake in the __pow__
method in the same file.
comment:31 follow-up: 32 Changed 9 years ago by
Replying to pbruin:
Here is one more guess: in
sage/rings/finite_rings/element_pari_ffelt.pyx
the Python intx
is first converted into a PARI t_INT as follows (lines 209-210):pari_catch_sig_on() x_GEN = (<pari_gen>pari(x)).gThe order of these two lines should be interchanged.
Before #15125, the second line was
x_GEN = stoi(x)
; herepari_catch_sig_on()
must be called first since we call the un-wrapped PARI function. However, now we callpari(x)
, which does its ownpari_catch_sig_on()...pari_catch_sig_off()
. As we know, the current error-handling code is non-reentrant. I don't see exactly how this could cause our bug, but maybe my imagination is too limited.
I agree that is a mistake, but on the other hand, we are not handling any errors here, so the non-reentrant error handling code isn't called. So that cannot explain the problem.
In the line
ret = ret + c
, could you replacec
bybase(c)
With that change, I no longer get the error (which unfortunately doesn't imply that the bug is fixed).
comment:32 follow-up: 36 Changed 9 years ago by
Replying to jdemeyer:
I agree that is a mistake, but on the other hand, we are not handling any errors here, so the non-reentrant error handling code isn't called. So that cannot explain the problem.
Probably true; the only sort of thing that I could imagine happening here is that PARI runs out of stack space, the call has to be restarted, and the error handler does a longjmp()
to the wrong stack frame. However, this can hardly be the problem, because nothing is using a lot of PARI memory here.
In the line
ret = ret + c
, could you replacec
bybase(c)
With that change, I no longer get the error (which unfortunately doesn't imply that the bug is fixed).
Mysterious. I checked that the coercion system does exactly the same thing internally, as it should (convert the Python int c
to pari_ffelt
and then add this to ret
in base
), so there is no other intermediate conversion that could go wrong.
comment:33 Changed 9 years ago by
Some more news from the debugging camp: I added
-
sage/rings/finite_rings/element_pari_ffelt.pyx
diff --git a/sage/rings/finite_rings/element_pari_ffelt.pyx b/sage/rings/finite_rings/element_pari_ffelt.pyx
a b 450 450 pari_catch_sig_on() 451 451 x.construct(FF_add((<FiniteFieldElement_pari_ffelt>self).val, 452 452 (<FiniteFieldElement_pari_ffelt>right).val)) 453 print "%s + %s = %s"%(self, right, x) 453 454 return x 454 455 455 456 cpdef ModuleElement _sub_(FiniteFieldElement_pari_ffelt self, ModuleElement right): … … 482 483 pari_catch_sig_on() 483 484 x.construct(FF_mul((<FiniteFieldElement_pari_ffelt>self).val, 484 485 (<FiniteFieldElement_pari_ffelt>right).val)) 486 print "%s * %s = %s"%(self, right, x) 485 487 return x 486 488 487 489 cpdef RingElement _div_(FiniteFieldElement_pari_ffelt self, RingElement right):
and adjusted some doctests. This clearly shows the error in the conversion to PARI:
sage -t devel/sage/sage/schemes/plane_conics/con_finite_field.py ********************************************************************** File "devel/sage/sage/schemes/plane_conics/con_finite_field.py", line 108, in sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.? Failed example: C = Conic([1, a, -5]); C Expected: a * 1 = a 0 + a = a 0 + 2 = 2 Projective Conic Curve over Finite Field in a of size 7^20 defined by x^2 + (a)*y^2 + 2*z^2 Got: a * 0 = 0 0 + 0 = 0 0 + 2 = 2 Projective Conic Curve over Finite Field in a of size 7^20 defined by x^2 + (a)*y^2 + 2*z^2 ********************************************************************** File "devel/sage/sage/schemes/plane_conics/con_finite_field.py", line 113, in sage.schemes.plane_conics.con_finite_field.ProjectiveConic_finite_field.? Failed example: C._coefficients Expected: [1, 0, 0, a, 0, 2] Got: [1, 0, 0, 0, 0, 2] **********************************************************************
comment:34 follow-up: 37 Changed 9 years ago by
If you have access to boxen, the build I use with these problems is in /release/sage-5.13.beta0
. You could probably copy that and experiment with it.
comment:35 Changed 9 years ago by
Replying to pbruin:
Here is one more guess: in
sage/rings/finite_rings/element_pari_ffelt.pyx
the Python intx
is first converted into a PARI t_INT as follows (lines 209-210):pari_catch_sig_on() x_GEN = (<pari_gen>pari(x)).gThe order of these two lines should be interchanged.
I just tried that, and it doesn't make the error go away.
comment:36 follow-up: 38 Changed 9 years ago by
Replying to pbruin:
In the line
ret = ret + c
, could you replacec
bybase(c)
With that change, I no longer get the error (which unfortunately doesn't imply that the bug is fixed).
Mysterious. I checked that the coercion system does exactly the same thing internally
How did you check? I think it's more and more likely that the coercion system is the problem here, because
1) The coercion system is notorious for generating hard-to-reproduce bugs since it relies on (hashes of) memory addresses.
2) Making the conversions explicit (see diff below) fixes the problem.
-
sage/libs/singular/singular.pyx
diff --git a/sage/libs/singular/singular.pyx b/sage/libs/singular/singular.pyx
a b 232 232 c = <long>napGetCoeff(z) 233 233 e = napGetExpFrom(z,1, _ring) 234 234 if e == 0: 235 ret = ret + c235 ret = ret + base(c) 236 236 elif c != 0: 237 ret = ret + c * a**e237 ret = ret + (a**e) * base(c) 238 238 z = <napoly*>pNext(<poly*>z) 239 239 return ret 240 240
comment:37 Changed 9 years ago by
Replying to jdemeyer:
If you have access to boxen, the build I use with these problems is in
/release/sage-5.13.beta0
. You could probably copy that and experiment with it.
OK, got it. It gave me a warning about unsupported ssse3 instructions, but at least the files in question don't seem to be affected.
comment:38 Changed 9 years ago by
Replying to jdemeyer:
Mysterious. I checked that the coercion system does exactly the same thing internally
How did you check? I think it's more and more likely that the coercion system is the problem here
I did the following (and I agree that this doesn't prove that the coercion always goes like this):
sage: F.<a>=FiniteField(7^20) sage: from sage.structure.coerce import CoercionModel_cache_maps sage: cm=CoercionModel_cache_maps() sage: cm.explain(a,int(0)) Coercion on right operand via Conversion map: From: Set of Python objects of type 'int' To: Finite Field in a of size 7^20 Arithmetic performed after coercions. Result lives in Finite Field in a of size 7^20 Finite Field in a of size 7^20
comment:39 follow-up: 42 Changed 9 years ago by
Got it! The following line is no good:
x_GEN = (<pari_gen>pari(x)).g
Python can destroy the object pari(x)
because there are no references to it (the pointer x_GEN
doesn't count as a reference for Python's garbage collecting).
Changed 9 years ago by
Attachment: | 14888_review.patch added |
---|
comment:41 Changed 9 years ago by
Authors: | Peter Bruin → Peter Bruin, Jeroen Demeyer |
---|---|
Description: | modified (diff) |
Status: | needs_work → needs_review |
comment:42 Changed 9 years ago by
Reviewers: | Jean-Pierre Flori, Jeroen Demeyer → Jean-Pierre Flori, Jeroen Demeyer, Peter Bruin |
---|
Replying to jdemeyer:
Got it! The following line is no good:
x_GEN = (<pari_gen>pari(x)).gPython can destroy the object
pari(x)
because there are no references to it (the pointerx_GEN
doesn't count as a reference for Python's garbage collecting).
Beautiful! I checked the C code generated by Cython and it does indeed decrease the reference count of this temporary object too early.
I have never been able to reproduce the bug, but I'm convinced that you nailed the problem. I'll run doctests and then give this a positive review.
comment:44 Changed 9 years ago by
Merged in: | → sage-5.13.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
switch to FiniteField_pari_ffelt; based on 5.11.beta3 + #12142