Opened 6 years ago
Closed 6 years ago
#20062 closed task (fixed)
Make _floordiv_() return the Euclidean quotient for power series over fields
Reported by:  pbruin  Owned by:  

Priority:  minor  Milestone:  sage7.1 
Component:  algebra  Keywords:  
Cc:  jdemeyer  Merged in:  
Authors:  Peter Bruin  Reviewers:  Bruno Grenet 
Report Upstream:  N/A  Work issues:  
Branch:  b7cd5cb (Commits, GitHub, GitLab)  Commit:  b7cd5cb0331479589f777c4da8fdd35c3bc1bb2b 
Dependencies:  Stopgaps: 
Description (last modified by )
There exists a method PowerSeries_poly.__floordiv__()
, but it is not clear how it differs from ordinary division (see comment:43:ticket:15601), or how it should differ mathematically.
We replace this method by a new method PowerSeries._floordiv_()
, which returns the Euclidean quotient over fields and is a deprecated alias for _div_()
over other rings.
Change History (16)
comment:1 Changed 6 years ago by
 Branch set to u/pbruin/20062PowerSeries_floordiv
 Commit set to e9719f7399ffab100407a360c16fe0596e7f2689
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:3 in reply to: ↑ 2 ; followup: ↓ 4 Changed 6 years ago by
Replying to bruno:
I don't fully agree with your proposal: In (generic) implementations for elements of rings, one may need to have a
__floordiv__
(which returns the same as__div__
).
Why would this be necessary? If the user calls __floordiv__
, he presumably does this for a reason, i.e. expects that it behaves differently from __div__
...
That's why (I guess) there is a
__floordiv__
in the classFieldElement
.
Well, power series rings are not fields. There is also an implementation of _floordiv_
in RingElement
, which explicitly raises an error saying unsupported operand parent(s) for '//'
. In fact, this error is even raised when applying __floordiv__
to elements of RR
:
sage: RR(1.2) // RR(2.3) ... TypeError: unsupported operand parent(s) for '//': 'Real Field with 53 bits of precision' and 'Real Field with 53 bits of precision'
So I would not deprecate it, but rather simply make it an (nondeprecated) alias of
__div__
.
Then we should do this in general for ring elements; I don't really see the advantage of this...
In my opinion, it would make more sense to make sure that power series rings R
over a field, or more generally all discrete valuation rings (R, v)
, are put into the category of Euclidean domains. Then floor division in R
can be implemented using Euclidean division, so f // g = f / g
if v(g) <= v(f)
and f // g = 0
if v(g) > v(f)
. However, this has the disadvantage that it is not the same as the current __floordiv__
, which (as far as I can see) is the same as __div__
.
comment:4 in reply to: ↑ 3 Changed 6 years ago by
Replying to pbruin:
Why would this be necessary? If the user calls
__floordiv__
, he presumably does this for a reason, i.e. expects that it behaves differently from__div__
...
One case I very often encounter is the need of an "exact division", that is a division when you know in advance that the result is exact.
That's why (I guess) there is a
__floordiv__
in the classFieldElement
.Well, power series rings are not fields. There is also an implementation of
_floordiv_
inRingElement
, which explicitly raises an error sayingunsupported operand parent(s) for '//'
. In fact, this error is even raised when applying__floordiv__
to elements ofRR
:sage: RR(1.2) // RR(2.3) ... TypeError: unsupported operand parent(s) for '//': 'Real Field with 53 bits of precision' and 'Real Field with 53 bits of precision'
Right. But this behavior for RR
is currently being discussed in #15260.
So I would not deprecate it, but rather simply make it an (nondeprecated) alias of
__div__
.Then we should do this in general for ring elements; I don't really see the advantage of this...
That's right, it is probably a bad idea to make __floordiv__
an alias of __div__
in this case.
In my opinion, it would make more sense to make sure that power series rings
R
over a field, or more generally all discrete valuation rings(R, v)
, are put into the category of Euclidean domains. Then floor division inR
can be implemented using Euclidean division, sof // g = f / g
ifv(g) <= v(f)
andf // g = 0
ifv(g) > v(f)
. However, this has the disadvantage that it is not the same as the current__floordiv__
, which (as far as I can see) is the same as__div__
.
You're perfectly right. My twocent on this would be as follows:
__div__
should return an element of the fraction field, as it is the case for elements ofZZ
or polynomials for instance; I find the current situation weird:while for instance forsage: R.<x> = QQ[[]] sage: (1/(1+x)).parent() Power Series Ring in x over Rational Field sage: (1/x).parent() Laurent Series Ring in x over Rational Field
ZZ
:sage: (1/1).parent() is (1/2).parent() True
__floordiv__
in power series rings over a field should return the quotient in the euclidean division, since these rings are euclidean.
__floordiv__
in power series rings overZZ
(say) should behave the same way as it behaves for polynomials overZZ
, that is return the quotient in the euclidean division (as overQQ
) but reducing each coefficient modulo the leading coefficient of the divisor. For instance,23*xx^2+O(x^3)//(2+x)
should equal12*x+0*x^2+O(x^3)
.
comment:5 followup: ↓ 6 Changed 6 years ago by
I tried to (1) add a method _floordiv_
to EuclideanDomains.ElementMethods
, and (2) make DiscreteValuationRings
a subcategory of EuclideanDomains
. However, f // g
then still complains that the parents do not support this operator. If I understand correctly, this is because RingElement._floordiv_
comes before EuclideanDomains.ElementMethods._floordiv_
in the method resolution order. We cannot remove the first one because it must be implemented in RingElement
, being a cpdef
method.
Jeroen, do you (as the author of e.g. #2034) perhaps know a way around this?
Edit: (2) was done in #20283.
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Replying to pbruin:
I tried to (1) add a method
_floordiv_
toEuclideanDomains.ElementMethods
I think that such category stuff should probably not be used for Cython methods, I'm not entirely surprised that it doesn't work.
In any case, I think there is not much point in implementing stuff if we haven't agreed on the semantics of //
.
comment:7 followup: ↓ 8 Changed 6 years ago by
 Status changed from needs_work to needs_review
After thinking about this a bit more, it still seems meaningful to me to have an operator //
that is different from /
, and that returns the "Euclidean" quotient in the case of power series over a field. (I am not sure what to do for power series over Z, for example).
However, both to warn users and because the "correct" //
seems to be nontrivial to implement, it is probably good to start by deprecating the current behaviour where //
behaves identically to /
. Hence I am setting this ticket back to "needs review" and propose to do the "meaningful" reimplementation of //
at a later time.
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 6 years ago by
Replying to pbruin:
After thinking about this a bit more, it still seems meaningful to me to have an operator
//
that is different from/
, and that returns the "Euclidean" quotient in the case of power series over a field. (I am not sure what to do for power series over Z, for example).However, both to warn users and because the "correct"
//
seems to be nontrivial to implement, it is probably good to start by deprecating the current behaviour where//
behaves identically to/
. Hence I am setting this ticket back to "needs review" and propose to do the "meaningful" reimplementation of//
at a later time.
Note that there exists a method quo_rem
for DiscreteValuationRing
s which works. Thus it should be possible to use it to get a method __floordiv__
. I am not sure to understand the subtleties described in comment:5 and comment:6, but at least there is some working code. For instance:
sage: R.<x> = QQ[[]] sage: R(1).quo_rem(1+t) (1  t + t^2  t^3 + t^4  t^5 + t^6  t^7 + t^8  t^9 + t^10  t^11 + t^12  t^13 + t^14  t^15 + t^16  t^17 + t^18  t^19 + O(t^20), 0)
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 6 years ago by
Replying to bruno:
Note that there exists a method
quo_rem
forDiscreteValuationRing
s which works.
Yes, I added that in #20283.
Thus it should be possible to use it to get a method
__floordiv__
. I am not sure to understand the subtleties described in comment:5 and comment:6, but at least there is some working code. For instance:sage: R.<x> = QQ[[]] sage: R(1).quo_rem(1+t) (1  t + t^2  t^3 + t^4  t^5 + t^6  t^7 + t^8  t^9 + t^10  t^11 + t^12  t^13 + t^14  t^15 + t^16  t^17 + t^18  t^19 + O(t^20), 0)
Yes, absolutely. There are two problems: (1) due to the problem mentioned in comment:5, it seems that we cannot easily implement a generic __floordiv__
using quo_rem
for all Euclidean domains simultaneously, and (2) in view of backward compatibility it would not be very good to change the behaviour of __floordiv__
without any warning or deprecation of the old behaviour.
comment:10 in reply to: ↑ 9 Changed 6 years ago by
Replying to pbruin:
Replying to bruno:
Note that there exists a method
quo_rem
forDiscreteValuationRing
s which works.Yes, I added that in #20283.
I did not notice that, so you probably knew this :)
.
Thus it should be possible to use it to get a method
__floordiv__
. I am not sure to understand the subtleties described in comment:5 and comment:6, but at least there is some working code. For instance:sage: R.<x> = QQ[[]] sage: R(1).quo_rem(1+t) (1  t + t^2  t^3 + t^4  t^5 + t^6  t^7 + t^8  t^9 + t^10  t^11 + t^12  t^13 + t^14  t^15 + t^16  t^17 + t^18  t^19 + O(t^20), 0)Yes, absolutely. There are two problems: (1) due to the problem mentioned in comment:5, it seems that we cannot easily implement a generic
__floordiv__
usingquo_rem
for all Euclidean domains simultaneously, and (2) in view of backward compatibility it would not be very good to change the behaviour of__floordiv__
without any warning or deprecation of the old behaviour.
Again, I simply trust you for the technical part about __floordiv__
. For the deprecation policy, I (probably) agree that we should warn the user. Isn't it possible to put a deprecation warning while changing the behavior? I mean, one could do something like:
 If
self.quo_rem(other)
works, returnself.quo_rem(other)[0]
;  Else return
self._div_(other)
;  In all cases, print a deprecation message such as (message to be improved for sure!):
The operator // now performs a euclidean division (when possible) rather than a division. Use / instead to perform a division.
Btw, I think that this change should also go with a change of behavior in the truediv
algorithm, that should always return an element of the fraction field of the PowerSeries? ring.
comment:11 Changed 6 years ago by
A proposal along the line of my previous comment would be as follows:
cpdef RingElement _floordiv_(self, RingElement denom): """ ... """ from sage.misc.superseded import deprecation try: deprecation(20062, "the operator // now performs a euclidean division for power series over fields, use / instead to perform a (true) division") return self.quo_rem(denom)[0] except AttributeError, NotImplementedError: deprecation(20062, "the operator // is deprecated for power series over nonfields, use / instead") return self._div_(denom)
Testing this code, I get a deprecation warning about deprecation warnings so it is probably not the right way to write this:
/opt/sage/local/lib/python2.7/sitepackages/IPython/core/formatters.py:92: DeprecationWarning: DisplayFormatter._ipython_display_formatter_default is deprecated: use @default decorator instead.
comment:12 Changed 6 years ago by
 Commit changed from e9719f7399ffab100407a360c16fe0596e7f2689 to 5e5748bdaf542f550aadd722d06925c668b473ab
Branch pushed to git repo; I updated commit sha1. New commits:
5e5748b  Trac 20062: make _floordiv_ do Euclidean division for power series over fields

comment:13 Changed 6 years ago by
 Description modified (diff)
 Summary changed from Make _floordiv_() for power series a deprecated alias for _div_() to Make _floordiv_() return the Euclidean quotient for power series over fields
The new comment implements a variant of your suggestion; I think the message in the case of fields should be a normal warning (since the behaviour changed), not a deprecation.
comment:14 Changed 6 years ago by
 Commit changed from 5e5748bdaf542f550aadd722d06925c668b473ab to b7cd5cb0331479589f777c4da8fdd35c3bc1bb2b
Branch pushed to git repo; I updated commit sha1. New commits:
b7cd5cb  Trac 20062: improvements related to imports

comment:15 Changed 6 years ago by
 Reviewers set to Bruno Grenet
 Status changed from needs_review to positive_review
This looks good to me!
comment:16 Changed 6 years ago by
 Branch changed from u/pbruin/20062PowerSeries_floordiv to b7cd5cb0331479589f777c4da8fdd35c3bc1bb2b
 Resolution set to fixed
 Status changed from positive_review to closed
I don't fully agree with your proposal: In (generic) implementations for elements of rings, one may need to have a
__floordiv__
(which returns the same as__div__
). That's why (I guess) there is a__floordiv__
in the classFieldElement
. So I would not deprecate it, but rather simply make it an (nondeprecated) alias of__div__
.