Make _floordiv_() return the Euclidean quotient for power series over fields

pjbruin commented 8 years ago

There exists a method PowerSeries_poly.__floordiv__(), but it is not clear how it differs from ordinary division (see #15601 comment:43), 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.

CC: @jdemeyer

Component: algebra

Author: Peter Bruin

Branch/Commit: b7cd5cb

Reviewer: Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/20062

pjbruin commented 8 years ago

Branch: u/pbruin/20062-PowerSeries_floordiv

pjbruin commented 8 years ago

Commit: e9719f7

bgrenet commented 8 years ago

comment:2

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 class FieldElement. So I would not deprecate it, but rather simply make it an (non-deprecated) alias of __div__.

pjbruin commented 8 years ago

comment:3

Replying to @bgrenet:

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 class FieldElement.

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 (non-deprecated) 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__.

bgrenet commented 8 years ago

comment:4

Replying to @pjbruin:

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 class FieldElement.

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'

Right. But this behavior for RR is currently being discussed in #15260.

So I would not deprecate it, but rather simply make it an (non-deprecated) 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 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__.

You're perfectly right. My two-cent on this would be as follows:

__div__ should return an element of the fraction field, as it is the case for elements of ZZ or polynomials for instance; I find the current situation weird:

sage: 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

while for instance for 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 over ZZ (say) should behave the same way as it behaves for polynomials over ZZ, that is return the quotient in the euclidean division (as over QQ) but reducing each coefficient modulo the leading coefficient of the divisor. For instance, 2-3*x-x<sup>2+O(x</sup>3)//(2+x) should equal 1-2*x+0*x<sup>2+O(x</sup>3).

pjbruin commented 8 years ago

comment:5

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.

jdemeyer commented 8 years ago

comment:6

Replying to @pjbruin:

I tried to (1) add a method _floordiv_ to EuclideanDomains.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 //.

pjbruin commented 8 years ago

comment:7

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 non-trivial 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.

bgrenet commented 8 years ago

comment:8

Replying to @pjbruin:

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 non-trivial 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 DiscreteValuationRings 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)

pjbruin commented 8 years ago

comment:9

Replying to @bgrenet:

Note that there exists a method quo_rem for DiscreteValuationRings 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.

bgrenet commented 8 years ago

comment:10

Replying to @pjbruin:

Replying to @bgrenet:

Note that there exists a method quo_rem for DiscreteValuationRings 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__ 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.

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, return self.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.

bgrenet commented 8 years ago

comment:11

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 non-fields, 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/site-packages/IPython/core/formatters.py:92: DeprecationWarning: DisplayFormatter._ipython_display_formatter_default is deprecated: use @default decorator instead.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from e9719f7 to 5e5748b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5e5748b Trac 20062: make `_floordiv_` do Euclidean division for power series over fields

pjbruin commented 8 years ago

comment:13

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.

pjbruin commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 There exists a method `PowerSeries_poly.__floordiv__()`, but it is not clear how it differs from ordinary division (see [#15601 comment:43](https://github.com/sagemath/sage/issues/15601#comment:43)), or how it should differ mathematically.

-We replace this method by a new method `PowerSeries._floordiv_()`, which is a deprecated alias for `_div_()`.
+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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 5e5748b to b7cd5cb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

b7cd5cb Trac 20062: improvements related to imports

bgrenet commented 8 years ago

Reviewer: Bruno Grenet

bgrenet commented 8 years ago

comment:15

This looks good to me!

vbraun commented 8 years ago

Changed branch from u/pbruin/20062-PowerSeries_floordiv to b7cd5cb

sagemath / sage

Make _floordiv_() return the Euclidean quotient for power series over fields #20062