Sage: Ticket #11685: Pari finite field extension: element created by list not recognised as zero
https://trac.sagemath.org/ticket/11685
<p>
In sage-4.7.1:
</p>
<pre class="wiki">sage: K.<a> = GF(3^11)
sage: K([])
0
sage: K([]) == 0
False
</pre><hr />
<p>
Apply
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11685/11685_against_4.7.2.alpha1.patch" title="Attachment '11685_against_4.7.2.alpha1.patch' in Ticket #11685">11685_against_4.7.2.alpha1.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11685/11685_against_4.7.2.alpha1.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11685/11685_referee.patch" title="Attachment '11685_referee.patch' in Ticket #11685">11685_referee.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11685/11685_referee.patch" title="Download"></a>
</li></ol><p>
to the Sage library.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11685
Trac 1.1.6johanbosmanFri, 12 Aug 2011 23:03:17 GMTsummary changed
https://trac.sagemath.org/ticket/11685#comment:1
https://trac.sagemath.org/ticket/11685#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>Pari finite field extension created by list not recognised as zero</em> to <em>Pari finite field extension: element created by list not recognised as zero</em>
</li>
</ul>
TicketjohanbosmanSat, 13 Aug 2011 10:39:31 GMTkeywords changed
https://trac.sagemath.org/ticket/11685#comment:2
https://trac.sagemath.org/ticket/11685#comment:2
<ul>
<li><strong>keywords</strong>
<em>pari</em> added
</li>
</ul>
TicketjohanbosmanSat, 13 Aug 2011 12:28:26 GMTattachment set
https://trac.sagemath.org/ticket/11685
https://trac.sagemath.org/ticket/11685
<ul>
<li><strong>attachment</strong>
set to <em>trac_11685_pari_zero_list.patch</em>
</li>
</ul>
TicketjohanbosmanSat, 13 Aug 2011 12:29:13 GMTstatus changed; author set
https://trac.sagemath.org/ticket/11685#comment:3
https://trac.sagemath.org/ticket/11685#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Johan Bosman</em>
</li>
</ul>
TicketSimonKingSun, 14 Aug 2011 13:51:47 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/11685#comment:4
https://trac.sagemath.org/ticket/11685#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
Looking at the value of the attribute <code>__value</code>, I can confirm that there has been a bug, and I can confirm that your patch fixes it. The fix is tested, and the long doctests of both devel/sage-main/doc and devel/sage-main/sage pass.
</p>
<p>
Hence, I give it a positive review.
</p>
TicketjdemeyerTue, 16 Aug 2011 12:30:54 GMTstatus, author changed
https://trac.sagemath.org/ticket/11685#comment:5
https://trac.sagemath.org/ticket/11685#comment:5
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>author</strong>
changed from <em>Johan Bosman</em> to <em>Johan Bosman, Jeroen Demeyer</em>
</li>
</ul>
<p>
I add an alternative patch which IMHO fixes the problem in a better way, adds more tests and simplifies some other code regarding zero elements.
</p>
TicketjdemeyerTue, 16 Aug 2011 12:30:58 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:6
https://trac.sagemath.org/ticket/11685#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjohanbosmanTue, 16 Aug 2011 13:09:41 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:7
https://trac.sagemath.org/ticket/11685#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There are doctests that fail:
</p>
<pre class="wiki">sage -t 1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed
</pre>
TicketjohanbosmanTue, 16 Aug 2011 13:11:54 GMTdescription changed
https://trac.sagemath.org/ticket/11685#comment:8
https://trac.sagemath.org/ticket/11685#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11685?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:7" title="Comment 7">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
There are doctests that fail:
</p>
<pre class="wiki">sage -t 1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed
</pre></blockquote>
<p>
In combination with the fixes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>, that is.
</p>
TicketjohanbosmanTue, 16 Aug 2011 13:25:56 GMTreviewer changed
https://trac.sagemath.org/ticket/11685#comment:9
https://trac.sagemath.org/ticket/11685#comment:9
<ul>
<li><strong>reviewer</strong>
changed from <em>Simon King</em> to <em>Simon King, Johan Bosman</em>
</li>
</ul>
TicketSimonKingTue, 16 Aug 2011 14:39:51 GMT
https://trac.sagemath.org/ticket/11685#comment:10
https://trac.sagemath.org/ticket/11685#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:8" title="Comment 8">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
In combination with the fixes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>, that is.
</p>
</blockquote>
<p>
If it is only in combination with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>, then please test whether the problem persists if only the patch from here is applied.
</p>
TicketjdemeyerTue, 16 Aug 2011 14:45:33 GMT
https://trac.sagemath.org/ticket/11685#comment:11
https://trac.sagemath.org/ticket/11685#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:8" title="Comment 8">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:7" title="Comment 7">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
There are doctests that fail:
</p>
<pre class="wiki">sage -t 1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed
</pre></blockquote>
<p>
In combination with the fixes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>, that is.
</p>
</blockquote>
<p>
Agreed. The problem here is the empty list <code>[]</code>. I did not realize this was a legal argument to the constructor.
</p>
TicketjdemeyerTue, 16 Aug 2011 15:03:21 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:12
https://trac.sagemath.org/ticket/11685#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjdemeyerTue, 16 Aug 2011 15:06:21 GMTdescription changed
https://trac.sagemath.org/ticket/11685#comment:13
https://trac.sagemath.org/ticket/11685#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11685?action=diff&version=13">diff</a>)
</li>
</ul>
TicketSimonKingTue, 16 Aug 2011 15:18:18 GMT
https://trac.sagemath.org/ticket/11685#comment:14
https://trac.sagemath.org/ticket/11685#comment:14
<p>
With <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11685/trac_11685_pari_zero_list.patch" title="Attachment 'trac_11685_pari_zero_list.patch' in Ticket #11685">trac_11685_pari_zero_list.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11685/trac_11685_pari_zero_list.patch" title="Download"></a>, we have (correctly)
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
Mod(Mod(0, 1152921504606847009), Mod(1, 1152921504606847009)*a^3 + Mod(1132330333307175281, 1152921504606847009)*a^2 + Mod(564283687250211459, 1152921504606847009)*a + Mod(455334297379199858, 1152921504606847009))
</pre><p>
With <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11685/11685.patch" title="Attachment '11685.patch' in Ticket #11685">11685.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11685/11685.patch" title="Download"></a>, that example fails as follows:
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))
---------------------------------------------------------------------------
PariError Traceback (most recent call last)
...
PariError: incorrect type (11)
</pre><p>
I think it <em>should</em> be possible to use the value of a pari element for the creation of a pari element. Hence, either we use the first patch, or the second patch needs work.
</p>
<p>
Perhaps, one could merge the two patches and use Johan's algorithm together with Jeroen's examples?
</p>
TicketSimonKingTue, 16 Aug 2011 15:31:07 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:15
https://trac.sagemath.org/ticket/11685#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketjdemeyerTue, 16 Aug 2011 15:51:06 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:16
https://trac.sagemath.org/ticket/11685#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
New code, new tests to implement Simon King's suggestion.
</p>
TicketSimonKingTue, 16 Aug 2011 16:13:19 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:17
https://trac.sagemath.org/ticket/11685#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
The error has changed, but there's still an error:
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
...
TypeError: unable to coerce
</pre><p>
<em>If</em> we want to make that kind of conversion work (perhaps Johan can express his point of view?) then something needs to be done.
</p>
TicketjohanbosmanTue, 16 Aug 2011 16:17:45 GMT
https://trac.sagemath.org/ticket/11685#comment:18
https://trac.sagemath.org/ticket/11685#comment:18
<p>
Also, we should keep speed in mind. I've done some timings:
</p>
<p>
With my patch:
</p>
<pre class="wiki">sage: K.<a> = GF(3^11)
sage: timeit('K([])')
625 loops, best of 3: 38.7 µs per loop
</pre><p>
With Jeroen's current patch:
</p>
<pre class="wiki">sage: K.<a> = GF(3^11)
sage: timeit('K([])')
625 loops, best of 3: 153 µs per loop
</pre>
TicketjohanbosmanTue, 16 Aug 2011 16:34:01 GMT
https://trac.sagemath.org/ticket/11685#comment:19
https://trac.sagemath.org/ticket/11685#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:17" title="Comment 17">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
The error has changed, but there's still an error:
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
...
TypeError: unable to coerce
</pre><p>
<em>If</em> we want to make that kind of conversion work (perhaps Johan can express his point of view?) then something needs to be done.
</p>
</blockquote>
<p>
Yes, I certainly think it is a good idea to have such a conversion work.
</p>
TicketSimonKingTue, 16 Aug 2011 16:35:21 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:20
https://trac.sagemath.org/ticket/11685#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
If both the stability and the timings speak for the first patch, then I'd say y'all should merge your two patches into one. I do believe that the doc tests from the second patch are more thorough, and it would also be nice to include the corner cases that came up in the discussion.
</p>
TicketSimonKingTue, 16 Aug 2011 16:35:31 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:21
https://trac.sagemath.org/ticket/11685#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketjdemeyerTue, 16 Aug 2011 16:49:21 GMT
https://trac.sagemath.org/ticket/11685#comment:22
https://trac.sagemath.org/ticket/11685#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:20" title="Comment 20">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
If both the stability and the timings speak for the first patch, then I'd say y'all should merge your two patches into one.
</p>
</blockquote>
<p>
I think that the fact that your example works for the first patch is an unintentional side-effect and not really an intended feature. I believe my code is much more clear and simple.
</p>
<p>
I believe that I am fixing much more than what the ticket requires, but I will fix my patch anyway.
</p>
TicketSimonKingTue, 16 Aug 2011 17:52:15 GMT
https://trac.sagemath.org/ticket/11685#comment:23
https://trac.sagemath.org/ticket/11685#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:22" title="Comment 22">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I think that the fact that your example works for the first patch is an unintentional side-effect and not really an intended feature.
</p>
</blockquote>
<p>
Intended or not doesn't matter. It is a feature, I think.
</p>
<blockquote class="citation">
<p>
I believe that I am fixing much more than what the ticket requires, ...
</p>
</blockquote>
<p>
Indeed it does, namely:
</p>
<pre class="wiki">sage: k.<x> = GF(3^11)
sage: k([ k(0),k(1) ])
x
sage: k([0,1/2])
2
sage: R.<y> = PolynomialRing(k)
sage: k([ R(0),R(1) ])
x
</pre><p>
It a strength of your patch that the examples above work (they wouldn't, with the other patch).
</p>
<p>
Do you see a way to make <em>both</em> work?
</p>
<p>
I wouldn't say that your patch is simpler, because you first convert into a list of prime field elements and then convert into pari; a double conversion, so it seems to me, tends to be fragile.
</p>
<p>
I mean, the only problem with <code>k([k([0])._FiniteField_ext_pariElement__value])</code> in your patch is the fact that the pari value (which, after all, is zero) can not be converted into the zero of a finite field. There could be a work around, such as
</p>
<pre class="wiki">value = [GFp(c) for c in value if c else GFp.zero_element()]
</pre><p>
Concerning speed, one should test whether <code>k([])</code> is the only case in which your patch is slower. Since you have a special case for <code>k([])</code> anyway, it would be perfectly fine to have a short-cut, such as
</p>
<pre class="wiki">if not value: # or value==[], if that's faster
self.__value = (pari(0) * parent._pari_one()).Mod(parent._pari_modulus())
</pre>
TicketjdemeyerTue, 16 Aug 2011 18:15:36 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:24
https://trac.sagemath.org/ticket/11685#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:23" title="Comment 23">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I mean, the only problem with <code>k([k([0])._FiniteField_ext_pariElement__value])</code> in your patch is the fact that the pari value (which, after all, is zero) can not be converted into the zero of a finite field.
</p>
</blockquote>
<p>
This is not true, because this problem is not specific to zero. The problem really is that conversion of PARI finite field elements to <code>ZZ</code> fails. I rewrote the PARI -> ZZ conversion to fix this (the old code used strings(!) for the conversion)
</p>
TicketjdemeyerTue, 16 Aug 2011 18:21:13 GMT
https://trac.sagemath.org/ticket/11685#comment:25
https://trac.sagemath.org/ticket/11685#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:23" title="Comment 23">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I wouldn't say that your patch is simpler, because you first convert into a list of prime field elements and then convert into pari; a double conversion, so it seems to me, tends to be fragile.
</p>
</blockquote>
<p>
I would rather argue the opposite: I break the conversion down to two simpler independent steps.
</p>
<p>
It is probably true that my code is slower, but it all depends on what you want. Pick two:
</p>
<ul><li>Fast code
</li><li>Simple code
</li><li>Code with many features
</li></ul>
TicketjdemeyerTue, 16 Aug 2011 18:38:09 GMT
https://trac.sagemath.org/ticket/11685#comment:26
https://trac.sagemath.org/ticket/11685#comment:26
<p>
Note that most of the timing overhead in my latest patch is due to the creation of the <code>FiniteField</code> object. Maybe we could add a <code>prime_field()</code> cached method and use that?
</p>
TicketjohanbosmanTue, 16 Aug 2011 19:00:11 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:27
https://trac.sagemath.org/ticket/11685#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Let me add that I discovered this bug while working on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>, which is a speed issue. Normally I don't care so much about speed, but in this case things are really *far* too slow already; we should definitely not make them any slower, especially since this is not necessary. Seemingly innocent computations in Sage are often dominated by enormous chains of type conversions rather than the actual computations they intend to be.
</p>
<p>
In conclusion: it may be a good idea to either use such a cached method or avoid creating <a class="missing wiki">FiniteFields?</a> at all. ;).
</p>
TicketSimonKingTue, 16 Aug 2011 19:22:44 GMT
https://trac.sagemath.org/ticket/11685#comment:28
https://trac.sagemath.org/ticket/11685#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:26" title="Comment 26">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Note that most of the timing overhead in my latest patch is due to the creation of the <code>FiniteField</code> object. Maybe we could add a <code>prime_field()</code> cached method and use that?
</p>
</blockquote>
<p>
There is a <code>prime_subfield()</code> method, and you are perfectly right that it ought to be a cached method. Hopefully someone finally manages to review <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a>: It would make cached methods <em>very</em> fast.
</p>
<p>
"Breaking down into two simpler steps" makes sense. But one should keep in mind that it will now be <em>two</em> steps that could break. And if you measure simplicity in lines of code: Both patches have six lines of code in the section we are now talking about (if I did not miscount).
</p>
<p>
Perhaps we should clarify what we want to do with a list.
</p>
<p>
Let K be a finite field that is not a prime field. To the very least, we want: If L is a list of elements of the prime subfield k of K then K(L) should first interprete L as the list of coefficients of a polynomial, and interprete the polynomial as an element of K.
</p>
<p>
Ideally, we also want to allow in L objects that can be converted into k, even though their parent is not k in the first place. We seem to disagree on how that conversion is best done.
</p>
<blockquote>
<p>
1) The first patch seems to argue that, ultimately, we want to put stuff into pari, and so we should start to put it into pari as soon as possible, and do all further conversions there: We can put a list of field elements into pari, and we can easily convert things like pari(K(0)) into an element of pari(k).
</p>
</blockquote>
<blockquote>
<p>
2) The second patch seems to argue that we are Sage programmers, and thus the conversion should follow Sage standards, not pari standards. Thus, k is a finite prime field in Sage, and we only accept things that can be converted into that prime field. Apparently, an element of pari(K) that happens to belong to pari(k) fails to convert into k, sadly.
</p>
</blockquote>
<p>
I think that both approaches are equally simple, and both approaches make sense.
</p>
<p>
So, I suggest to decide based on (a) speed and (b) generality. (b) could be problematic, since at the moment we have examples that only work with the first patch and examples that only work with the second patch.
</p>
<p>
According to Johan, things are already quite slow, so, speed should really matter most.
</p>
<p>
By the way, I'd prefer fast code with many features, if I can pick only two out of three...
</p>
TicketjdemeyerWed, 17 Aug 2011 10:18:30 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:29
https://trac.sagemath.org/ticket/11685#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
New patch uses PARI if possible with a generic fallback if PARI fails. This should be quite fast and still work in general.
</p>
TicketjohanbosmanWed, 17 Aug 2011 12:08:41 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:30
https://trac.sagemath.org/ticket/11685#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
The patch passes all long doctests, the speed is okay, and it works in combination with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a>. Conclusion: positive review. :).
</p>
TicketSimonKingWed, 17 Aug 2011 12:57:50 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:31
https://trac.sagemath.org/ticket/11685#comment:31
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I tend to a positive review as well.
</p>
<p>
However, I have one question (thus "needs info"): Why did you remove the <code>if not check: ...</code> section? If one knows that the input is sane then it is very common to use <code>check=False</code> in order to save time.
</p>
TicketjdemeyerWed, 17 Aug 2011 13:05:37 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:32
https://trac.sagemath.org/ticket/11685#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:31" title="Comment 31">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I tend to a positive review as well.
</p>
<p>
However, I have one question (thus "needs info"): Why did you remove the <code>if not check: ...</code> section? If one knows that the input is sane then it is very common to use <code>check=False</code> in order to save time.
</p>
</blockquote>
<p>
1) That option and the code was completely undocumented and the purpose is not clear.
</p>
<p>
2) The logic seems backward: executing more code when <em>not</em> checking?
</p>
<p>
3) The <code></code>check<code></code> code changes the functionality of the function, which is usually not desired. To me checking should be something read-only, checking for invalid input and throwing exceptions. But not modifying the input.
</p>
<p>
4) the <code></code>check<code></code> code is related to the handling of zero inputs which is anyway handled separately in the code below.
</p>
TicketSimonKingWed, 17 Aug 2011 14:20:57 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:33
https://trac.sagemath.org/ticket/11685#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
First of all, note that the option <code>check==False</code> is used, as you can see by studying the arithmetic operations on finite field elements. And it is clearly beneficial! For example:
</p>
<p>
Without patches, I get
</p>
<pre class="wiki">sage: K.<a> = GF(5^9)
sage: b = 4*a^7 + 2*a^5 + 4*a^4 + 4*a^3 + 3*a^2 + 3*a
sage: %timeit b+3 # here, you will find that "check=False".
625 loops, best of 3: 30.9 µs per loop
sage: %timeit copy(b)
625 loops, best of 3: 14.3 µs per loop
</pre><p>
With your patch, it takes 42 µs resp. 25.9 µs per loop.
</p>
<p>
25-30% difference is relevant. Thus, I'd prefer to keep the "check=False" code.
</p>
<p>
Moreover, I can still not understand your rationale for removing the code:
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:32" title="Comment 32">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
1) That option and the code was completely undocumented and the purpose is not clear.
</p>
</blockquote>
<p>
If code is not documented then it should be documented, not removed.
</p>
<p>
The purpose is very clear: Provide better speed by avoiding any tests (or conversions, in this case). I think it is fairly common to have that option in Sage, of course for internal use only.
</p>
<p>
The price to pay for the speed is that one needs to provide very specific input: It must be pari.
</p>
<blockquote class="citation">
<p>
2) The logic seems backward: executing more code when <em>not</em> checking?
</p>
</blockquote>
<p>
You can't be serious.
</p>
<p>
If one has <code>check=False</code> then one just has
</p>
<pre class="wiki"> if not check:
if not value: # see comment below about this workaround
self.__value = pari(0).Mod(parent._pari_modulus())*parent._pari_one()
else:
self.__value = value
return
</pre><p>
and nothing more: Note the "return" in the last line.
</p>
<blockquote class="citation">
<p>
3) The <code></code>check<code></code> code changes the functionality of the function, which is usually not desired.
</p>
</blockquote>
<p>
It is quite usual that the check option does change the behaviour of the function, in the sense that a very specific input is expected, and it is not tested whether the user really got it right.
</p>
<p>
Here, check=False means that the input must be an element in the pari interface. Only since "zero" is a special case (see comments in the code), you have the test "if not value". As a side effect, the input <code>[]</code> or <code>None</code> or <code>False</code> would result in a zero element as well.
</p>
<blockquote class="citation">
<blockquote>
<p>
To me checking should be something read-only, checking for invalid input and throwing exceptions. But not modifying the input.
</p>
</blockquote>
</blockquote>
<p>
Sometimes you have two separate options <code>check</code> and <code>coerce</code>. Here, indeed, checking means that the input is also converted, when necessary. <code>convert_to_pari</code> might be a better name than <code>check</code>.
</p>
<p>
But since it is for internal use anyway, I see not much reason to change the name.
</p>
<blockquote class="citation">
<p>
4) the <code></code>check<code></code> code is related to the handling of zero inputs which is anyway handled separately in the code below.
</p>
</blockquote>
<p>
No. The check code simply provides a short cut for pari input. Only since pari is inconsistent in the way how different types of zero are dealt with, a special case is needed.
</p>
<p>
I suggest to use your patch without removing the <code>if check:</code> part. Can you please update it? And since the arguments of the <code>__init__</code> method are not documented at all, I suggest that I create a referee patch that fixes the documentation.
</p>
TicketjdemeyerWed, 17 Aug 2011 14:52:38 GMT
https://trac.sagemath.org/ticket/11685#comment:34
https://trac.sagemath.org/ticket/11685#comment:34
<p>
<a class="missing wiki">SimonKing?</a>: I agree with your comments, I somehow totally misread the <code></code>check=False<code></code> code.
</p>
TicketSimonKingWed, 17 Aug 2011 15:55:57 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:35
https://trac.sagemath.org/ticket/11685#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I see, so you change <code>check</code> into <code>value_from_pari</code>. So, I'll change my (not yet submitted) referee patch accordingly, and will run full doc tests. And then it'll hopefully be fine...
</p>
TicketSimonKingWed, 17 Aug 2011 16:02:21 GMT
https://trac.sagemath.org/ticket/11685#comment:36
https://trac.sagemath.org/ticket/11685#comment:36
<p>
I see that you just do
</p>
<pre class="wiki">if value_from_pari:
self.__value = value
</pre><p>
without a special case for a vanishing value.
</p>
<p>
I assume that the special case <code>if not value:</code> was there on purpose. Let's see what the tests say...
</p>
TicketSimonKingWed, 17 Aug 2011 16:48:28 GMTattachment set
https://trac.sagemath.org/ticket/11685
https://trac.sagemath.org/ticket/11685
<ul>
<li><strong>attachment</strong>
set to <em>11685_referee.patch</em>
</li>
</ul>
<p>
Referee patch, adding documentation
</p>
TicketSimonKingWed, 17 Aug 2011 16:53:55 GMTstatus, description changed
https://trac.sagemath.org/ticket/11685#comment:37
https://trac.sagemath.org/ticket/11685#comment:37
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11685?action=diff&version=37">diff</a>)
</li>
</ul>
<p>
The tests pass, hence, it was not necessary to have a special case for zero if <code>value_from_pari==True</code>.
</p>
<p>
I have attached a referee patch, that documents the arguments and adds a few examples. I hope my words are clear and concise enough, as the possible input can be very different.
</p>
<p>
If you think that my referee patch needs work, then feel free to complain.
</p>
<p>
Apply 11685.patch 11685_referee.patch
</p>
TicketjdemeyerWed, 17 Aug 2011 16:58:07 GMT
https://trac.sagemath.org/ticket/11685#comment:38
https://trac.sagemath.org/ticket/11685#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:36" title="Comment 36">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I assume that the special case <code>if not value:</code> was there on purpose. Let's see what the tests say...
</p>
</blockquote>
<p>
I guess the special case was needed precisely because of some earlier badly-initialized zero. If we don't start with a bad zero, we cannot somehow end up with a bad zero (I hope).
</p>
TicketjdemeyerMon, 22 Aug 2011 16:04:24 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:39
https://trac.sagemath.org/ticket/11685#comment:39
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I changed the patch by re-enabling the use of PARI's exponentiation. There was a warning which does not apply any more. The only change is in the <code>__pow__()</code> method, needs review.
</p>
TicketjdemeyerMon, 22 Aug 2011 16:04:31 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:40
https://trac.sagemath.org/ticket/11685#comment:40
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjdemeyerMon, 22 Aug 2011 16:08:01 GMTattachment set
https://trac.sagemath.org/ticket/11685
https://trac.sagemath.org/ticket/11685
<ul>
<li><strong>attachment</strong>
set to <em>11685.patch</em>
</li>
</ul>
<p>
New alternative patch, rewrites PARI->Integer coercion, fast and many features
</p>
TicketjohanbosmanWed, 24 Aug 2011 12:09:50 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:41
https://trac.sagemath.org/ticket/11685#comment:41
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I do get some fuzz applying the patch to sage-4.6.2.alpha1:
</p>
<pre class="wiki">applying 11685.patch
patching file sage/rings/integer.pyx
Hunk #2 succeeded at 3081 with fuzz 2 (offset 2525 lines).
Hunk #4 succeeded at 610 with fuzz 2 (offset -24 lines).
now at: 11685.patch
</pre><p>
How bad is that?
</p>
TicketSimonKingWed, 24 Aug 2011 12:44:13 GMT
https://trac.sagemath.org/ticket/11685#comment:42
https://trac.sagemath.org/ticket/11685#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:41" title="Comment 41">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
I do get some fuzz applying the patch to sage-4.6.2.alpha1:
</p>
</blockquote>
<p>
Do you mean "sage-4.7.2.alpha1" (not 4.6.2 but 4.7.2)?
</p>
<blockquote class="citation">
<p>
Hunk <a class="closed ticket" href="https://trac.sagemath.org/ticket/2" title="enhancement: Notebook locking (closed: fixed)">#2</a> succeeded at 3081 with fuzz 2 (offset 2525 lines).
Hunk <a class="closed ticket" href="https://trac.sagemath.org/ticket/4" title="defect: should exist a conversion from Integers(p**N) to pAdicField(p) (closed: fixed)">#4</a> succeeded at 610 with fuzz 2 (offset -24 lines).
</p>
</blockquote>
<p>
If I remember correctly, fuzz 2 will not be accepted by the release manager, because it is not improbable that the patch was applied in the wrong location - in particular when the offset is a couple of thousand lines.
</p>
TicketjohanbosmanWed, 24 Aug 2011 12:59:04 GMT
https://trac.sagemath.org/ticket/11685#comment:43
https://trac.sagemath.org/ticket/11685#comment:43
<blockquote class="citation">
<p>
Do you mean "sage-4.7.2.alpha1" (not 4.6.2 but 4.7.2)?
</p>
</blockquote>
<p>
Yes, I meant that indeed. :).
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Hunk <a class="closed ticket" href="https://trac.sagemath.org/ticket/2" title="enhancement: Notebook locking (closed: fixed)">#2</a> succeeded at 3081 with fuzz 2 (offset 2525 lines).
Hunk <a class="closed ticket" href="https://trac.sagemath.org/ticket/4" title="defect: should exist a conversion from Integers(p**N) to pAdicField(p) (closed: fixed)">#4</a> succeeded at 610 with fuzz 2 (offset -24 lines).
</p>
</blockquote>
<p>
If I remember correctly, fuzz 2 will not be accepted by the release manager, because it is not improbable that the patch was applied in the wrong location - in particular when the offset is a couple of thousand lines.
</p>
</blockquote>
<p>
Okay, so in that case it needs to be rebased.
</p>
TicketjohanbosmanSun, 28 Aug 2011 16:53:22 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:44
https://trac.sagemath.org/ticket/11685#comment:44
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
I've uploaded a rebased patch. If someone can double-check it, then we can give this ticket a positive review again.
</p>
TicketjdemeyerSun, 28 Aug 2011 21:23:36 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:45
https://trac.sagemath.org/ticket/11685#comment:45
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
negative_review because the patch is applied in the wrong place (as was hinted in a comment above).
</p>
TicketjohanbosmanSun, 28 Aug 2011 21:33:31 GMT
https://trac.sagemath.org/ticket/11685#comment:46
https://trac.sagemath.org/ticket/11685#comment:46
<p>
What do you mean by "applied in the wrong place"?
</p>
TicketjohanbosmanWed, 31 Aug 2011 12:55:33 GMTattachment set
https://trac.sagemath.org/ticket/11685
https://trac.sagemath.org/ticket/11685
<ul>
<li><strong>attachment</strong>
set to <em>11685_against_4.7.2.alpha1.patch</em>
</li>
</ul>
<p>
11685.patch rebased against sage-4.7.2.alpha1
</p>
TicketjohanbosmanWed, 31 Aug 2011 12:56:42 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:47
https://trac.sagemath.org/ticket/11685#comment:47
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
It appears that I'm blind. :P. Second try. ;).
</p>
TicketSimonKingThu, 08 Sep 2011 15:00:48 GMT
https://trac.sagemath.org/ticket/11685#comment:48
https://trac.sagemath.org/ticket/11685#comment:48
<p>
What patches are to be applied? That's to say, shouldn't the ticket description be changed, so that 11685_against_4.7.2.alpha1.patch is applied instead of 11685.patch?
</p>
TicketjohanbosmanThu, 08 Sep 2011 15:51:00 GMT
https://trac.sagemath.org/ticket/11685#comment:49
https://trac.sagemath.org/ticket/11685#comment:49
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:48" title="Comment 48">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
What patches are to be applied? That's to say, shouldn't the ticket description be changed, so that 11685_against_4.7.2.alpha1.patch is applied instead of 11685.patch?
</p>
</blockquote>
<p>
That depends on the release manager, I guess. I do not really know which of those 2 patches should be in the description, i.e. either the patch that applies against the latest stable release or the patch that applies against the latest alpha release. But in any case, 11685_against_4.7.2.alpha1.patch is most likely the one that is going to be applied.
</p>
TicketleifMon, 12 Sep 2011 11:50:42 GMTdescription changed
https://trac.sagemath.org/ticket/11685#comment:50
https://trac.sagemath.org/ticket/11685#comment:50
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11685?action=diff&version=50">diff</a>)
</li>
</ul>
<p>
Latest devel of course.
</p>
TicketleifMon, 12 Sep 2011 11:52:13 GMT
https://trac.sagemath.org/ticket/11685#comment:51
https://trac.sagemath.org/ticket/11685#comment:51
<p>
Anyone to review this? <a class="closed ticket" href="https://trac.sagemath.org/ticket/11684" title="defect: Obtaining coefficients of polynomials over finite fields is extremely slow (closed: fixed)">#11684</a> depends on it.
</p>
TicketpbruinTue, 13 Sep 2011 09:40:36 GMTreviewer changed
https://trac.sagemath.org/ticket/11685#comment:52
https://trac.sagemath.org/ticket/11685#comment:52
<ul>
<li><strong>reviewer</strong>
changed from <em>Simon King, Johan Bosman</em> to <em>Simon King, Johan Bosman, Peter Bruin</em>
</li>
</ul>
<p>
I have read the patches, applied them, checked by hand whether it worked and tested the whole Sage installation. Everything runs without problems in version 4.7.1. I am now going to test it with 4.7.2.alpha1 before giving it a positive review.
</p>
TicketjohanbosmanTue, 13 Sep 2011 10:00:38 GMT
https://trac.sagemath.org/ticket/11685#comment:53
https://trac.sagemath.org/ticket/11685#comment:53
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:52" title="Comment 52">pbruin</a>:
</p>
<blockquote class="citation">
<p>
I have read the patches, applied them, checked by hand whether it worked and tested the whole Sage installation. Everything runs without problems in version 4.7.1. I am now going to test it with 4.7.2.alpha1 before giving it a positive review.
</p>
</blockquote>
<p>
FYI: the patch against 4.7.2.alpha1 should also work against 4.7.2.alpha2, which is the most recent development version. ;)
</p>
TicketpbruinTue, 13 Sep 2011 13:42:52 GMT
https://trac.sagemath.org/ticket/11685#comment:54
https://trac.sagemath.org/ticket/11685#comment:54
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11685#comment:53" title="Comment 53">johanbosman</a>:
</p>
<blockquote class="citation">
<p>
FYI: the patch against 4.7.2.alpha1 should also work against 4.7.2.alpha2, which is the most recent development version. ;)
</p>
</blockquote>
<p>
OK, I'm now testing it with 4.7.2.alpha2 instead.
</p>
TicketpbruinWed, 14 Sep 2011 09:32:31 GMTstatus changed
https://trac.sagemath.org/ticket/11685#comment:55
https://trac.sagemath.org/ticket/11685#comment:55
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
All tests passed in 4.7.2.alpha2 as well, so I'm giving it a positive review.
</p>
TicketleifSat, 17 Sep 2011 05:04:55 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11685#comment:56
https://trac.sagemath.org/ticket/11685#comment:56
<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>merged</strong>
set to <em>sage-4.7.2.alpha3</em>
</li>
</ul>
Ticket