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

Status badges

Description (last modified by pbruin)

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 pbruin

  • Branch set to u/pbruin/20062-PowerSeries_floordiv
  • Commit set to e9719f7399ffab100407a360c16fe0596e7f2689
  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by bruno

  • Status changed from needs_review to needs_work

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__.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 6 years ago by pbruin

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 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__.

comment:4 in reply to: ↑ 3 Changed 6 years ago by bruno

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 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^2+O(x^3)//(2+x) should equal 1-2*x+0*x^2+O(x^3).

comment:5 follow-up: Changed 6 years ago by pbruin

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.

Last edited 6 years ago by pbruin (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 6 years ago by jdemeyer

Replying to pbruin:

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 //.

comment:7 follow-up: Changed 6 years ago by pbruin

  • 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 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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by bruno

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 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)

comment:9 in reply to: ↑ 8 ; follow-up: Changed 6 years ago by pbruin

Replying to bruno:

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.

comment:10 in reply to: ↑ 9 Changed 6 years ago by bruno

Replying to pbruin:

Replying to bruno:

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.

Last edited 6 years ago by bruno (previous) (diff)

comment:11 Changed 6 years ago by bruno

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.

comment:12 Changed 6 years ago by git

  • Commit changed from e9719f7399ffab100407a360c16fe0596e7f2689 to 5e5748bdaf542f550aadd722d06925c668b473ab

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

5e5748bTrac 20062: make _floordiv_ do Euclidean division for power series over fields

comment:13 Changed 6 years ago by pbruin

  • 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 git

  • Commit changed from 5e5748bdaf542f550aadd722d06925c668b473ab to b7cd5cb0331479589f777c4da8fdd35c3bc1bb2b

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

b7cd5cbTrac 20062: improvements related to imports

comment:15 Changed 6 years ago by bruno

  • 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 vbraun

  • Branch changed from u/pbruin/20062-PowerSeries_floordiv to b7cd5cb0331479589f777c4da8fdd35c3bc1bb2b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.