Sage: Ticket #10304: PolynomialRing_field.lagrange_polynomial doesn't always return a polynomial
http://trac.sagemath.org/ticket/10304
<p>
The function <tt>PolynomialRing_field.lagrange_polynomial</tt> sometimes returns an element of the coefficient ring or even a python int instead of an element of the polynomial ring. This can lead to problems if the caller was expecting a polynomial.
</p>
<pre class="wiki">sage: R, t = FractionField(QQ['t']).objgen(); R.rename('R')
sage: S, x = R['x'].objgen(); S.rename('S')
sage: S.lagrange_polynomial([(2, 3 * t), (4, t + 1)]).parent()
S
sage: S.lagrange_polynomial([(2, 3 * t)]).parent()
R
sage: type(S.lagrange_polynomial([]))
<type 'int'>
</pre><p>
The return value is a python int if the list of points was empty, an element of the base ring if the list of points had one point, and an element of the polynomial ring if the list of points had more than one point.
</p>
<p>
There are similar problems with the base case for the <tt>algorithm='neville'</tt> version:
</p>
<pre class="wiki">sage: S.lagrange_polynomial([(2, 3 * t), (4, t + 1)], algorithm='neville')
[t + 1, (-t + 1/2)*x + 5*t - 1]
sage: [poly.parent() for poly in _]
[R, S]
sage: S.lagrange_polynomial([(2, 3 * t)], algorithm='neville')
[3*t]
sage: [poly.parent() for poly in _]
[R]
sage: S.lagrange_polynomial([], algorithm='neville')
0
sage: type(_)
<type 'int'>
</pre><p>
Note that in this case, the return value is not even a list when the list of points was empty.
</p>
<p>
<strong>Apply:</strong>
</p>
<ol><li><a class="attachment" href="http://trac.sagemath.org/attachment/ticket/10304/trac_10304_lagrange_poly_in_self.patch" title="Attachment 'trac_10304_lagrange_poly_in_self.patch' in Ticket #10304">trac_10304_lagrange_poly_in_self.patch</a><a class="trac-rawlink" href="http://trac.sagemath.org/raw-attachment/ticket/10304/trac_10304_lagrange_poly_in_self.patch" title="Download"></a>
</li><li><a class="attachment" href="http://trac.sagemath.org/attachment/ticket/10304/trac-10304_reviewer.patch" title="Attachment 'trac-10304_reviewer.patch' in Ticket #10304">trac-10304_reviewer.patch</a><a class="trac-rawlink" href="http://trac.sagemath.org/raw-attachment/ticket/10304/trac-10304_reviewer.patch" title="Download"></a>
</li></ol>en-usSagehttp://trac.sagemath.org/chrome/site/sage_logo_trac_v2.png
http://trac.sagemath.org/ticket/10304
Trac 1.1.1mguaypaqSun, 21 Nov 2010 05:38:05 GMTattachment set
http://trac.sagemath.org/ticket/10304
http://trac.sagemath.org/ticket/10304
<ul>
<li><strong>attachment</strong>
set to <em>trac_10304_lagrange_poly_in_self.patch</em>
</li>
</ul>
TicketmguaypaqSun, 21 Nov 2010 05:52:02 GMTstatus changed; cc, author set
http://trac.sagemath.org/ticket/10304#comment:1
http://trac.sagemath.org/ticket/10304#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>cc</strong>
<em>mvngu</em> added
</li>
<li><strong>author</strong>
set to <em>Mathieu Guay-Paquet</em>
</li>
</ul>
<p>
I've put up a patch that should fix the problem, at least in the case of <tt>algorithm='divided_difference'</tt>, and includes a new doctest to verify this.
</p>
<p>
For the <tt>algorithm='neville'</tt> case, I've taken the liberty of rewriting the code, to clean it up and unify it a bit in addition to fixing the original problem. However:
</p>
<ul><li>This changes the default value of <tt>previous_row</tt> from <tt>None</tt> to <tt>[]</tt>. I doubt this would break anything, but it is a slight change in the function signature.
</li><li>In the case of an empty list of points, I wasn't sure whether to return <tt>[]</tt> or <tt>[0]</tt>. The former is more consistent with the <tt>previous_row</tt> option, but the latter preserves the property that the last element of the returned list is the interpolating polynomial (as opposed to non-existent). I opted for the first one, but there's definitely a choice to be made here. (I'll note that neither choice is really backwards-incompatible, since the method used to fail in this case.)
</li></ul><p>
Minh, I've put you on CC, since (I think) you wrote the original code for the <tt>algorithm='neville'</tt> part. Do you approve of the changes?
</p>
TicketmvnguSun, 21 Nov 2010 14:05:29 GMTattachment set
http://trac.sagemath.org/ticket/10304
http://trac.sagemath.org/ticket/10304
<ul>
<li><strong>attachment</strong>
set to <em>trac-10304_reviewer.patch</em>
</li>
</ul>
TicketmvnguSun, 21 Nov 2010 14:09:36 GMTdescription changed; reviewer set
http://trac.sagemath.org/ticket/10304#comment:2
http://trac.sagemath.org/ticket/10304#comment:2
<ul>
<li><strong>reviewer</strong>
set to <em>Minh Van Nguyen</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10304?action=diff&version=2">diff</a>)
</li>
</ul>
<p>
I'm happy with most of <a class="attachment" href="http://trac.sagemath.org/attachment/ticket/10304/trac_10304_lagrange_poly_in_self.patch" title="Attachment 'trac_10304_lagrange_poly_in_self.patch' in Ticket #10304">trac_10304_lagrange_poly_in_self.patch</a><a class="trac-rawlink" href="http://trac.sagemath.org/raw-attachment/ticket/10304/trac_10304_lagrange_poly_in_self.patch" title="Download"></a>, but here are some problems with that patch:
</p>
<ul><li>A standard idiom in Python is to avoid using a mutable object for a default value. Using a mutable object (such as a list) as a default value can introduce subtle and difficult to track bugs. See <a class="ext-link" href="http://effbot.org/zone/default-values.htm"><span class="icon"></span>this blog post</a> for an explanation of why one should avoid using mutable values for default arguments. See this section in the Python Language Reference for an official explanation about avoiding the use of mutable objects for default values.
</li></ul><p>
</p>
<ul><li>When you provide doctests that purports to illustrate that a bug has been fixed, you need to provide the corresponding ticket number in the documentation of the doctests.
</li></ul><p>
</p>
<ul><li>The docstring you introduce doesn't use proper ReST syntax.
</li></ul><p>
The reviewer patch <a class="attachment" href="http://trac.sagemath.org/attachment/ticket/10304/trac-10304_reviewer.patch" title="Attachment 'trac-10304_reviewer.patch' in Ticket #10304">trac-10304_reviewer.patch</a><a class="trac-rawlink" href="http://trac.sagemath.org/raw-attachment/ticket/10304/trac-10304_reviewer.patch" title="Download"></a> fixes all of the above issues. If you're OK with my patch, then set the ticket to positive review. See the ticket description for instructions on which patches to apply and in which order.
</p>
TicketmguaypaqTue, 23 Nov 2010 00:07:39 GMTstatus changed
http://trac.sagemath.org/ticket/10304#comment:3
http://trac.sagemath.org/ticket/10304#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I thought the use of a mutable default was safe, since it is always copied, never modified. But since there's an idiom against this, I'm happy to comply! And thanks for fixing the documentation issues.
</p>
<p>
Positive review for the reviewer patch.
</p>
TicketjdemeyerThu, 02 Dec 2010 16:11:01 GMTstatus changed; resolution, merged set
http://trac.sagemath.org/ticket/10304#comment:4
http://trac.sagemath.org/ticket/10304#comment:4
<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.6.1.alpha3</em>
</li>
</ul>
Ticket