Floor (integer) division of reals and rationals

[ncohen]

As reported in [1] and [2]

sage: x = 1/2 
sage: x//2 
1/4
sage: RDF(5) // 2
2.5
sage: RIF(5) // 2
TypeError: unsupported operand type(s) for //: 'sage.rings.real_mpfi.RealIntervalFieldElement' and 'sage.rings.real_mpfi.RealIntervalFieldElement'
sage: QQ(7) // QQ(3)
7/3

[1] ​https://groups.google.com/d/topic/sage-support/xE_S3WbFHzA/discussion [2] ​https://groups.google.com/d/msg/sage-devel/nQDAMtqnEsY/HfpIdvc9AwAJ

[tmonteil]

The reason is that for rationals (and apparently more generally for FieldElement), we have

    def __floordiv__(self, other):
        return self / other

where it should be

    def __floordiv__(self, other):
        return floor(self / other)

I will do a patch once i have compiled a more recent version of Sage

What is fun is that

sage: RDF(0.5)//2
0.25

sage: RR(0.5)//2
TypeError: unsupported operand type(s) for //: 'sage.rings.real_mpfr.RealLiteral' and 'sage.rings.real_mpfr.RealNumber'

[jkeitel]

Here's a branch that does this and implements a simple floordiv method for RR.

---

New commits:

​c9146be	Fix floordiv of FieldElements.
​fd78ca5	Floordiv for real_mpfr.

[jdemeyer]

New commits:

​fc5bca9

RR floordiv: fix rounding

[jdemeyer]

Using the floor() function for every field is a bad idea, for many fields taking floor() does not make sense.

[git]

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

​b49487a

Revert generic __floordiv__, add __floordiv__ for rationals

[jdemeyer]

I suggest just making the fixes for reals and rationals and deferring the discussion about a generic __floordiv__ to #2034.

[jdemeyer]

Running doctests now...

[jdemeyer]

Tests passed, needs review.

[tmonteil]

Could the fix work at least for RDF and RIF ? The current situation is:

sage: RDF(5) // 2
2.5

sage: RIF(5) // 2
TypeError: unsupported operand type(s) for //: 'sage.rings.real_mpfi.RealIntervalFieldElement' and 'sage.rings.real_mpfi.RealIntervalFieldElement'

[git]

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

​a7dde8b

Add __floordiv__ for RDF and RIF

[tmonteil]

The condition if not other != 0: looks weird. For real interval fields, why not using other.contains_zero() which is both easier to understand and faster ?

I do not understand the ad-hoc coercion that is made for RealNumber where the precision of self takes predecence over the one of other.

Concerning FieldElement it is very dangerous to return the usual division, since it will silently fail when the field in a subset of the reals for which we did not define a __floordiv__ method:

sage: RLF(5) // 2
2.5000000000000000?
sage: AA(5) // 2
5/2

What about trying (self/other).floor() and raising a NotImplementedError if the method does not exist ?

[jdemeyer]

Replying to tmonteil:

The condition if not other != 0: looks weird. For real interval fields, why not using other.contains_zero() which is both easier to understand and faster ?

Because I wanted something which behaves like contains_zero() but still works for any kind of element (unfortunately, __floordiv__ doesn't use the coercion system).

Concerning FieldElement it is very dangerous to return the usual division, since it will silently fail when the field in a subset of the reals for which we did not define a __floordiv__ method:

What about trying (self/other).floor() and raising a NotImplementedError if the method does not exist ?

That's outside the scope of this ticket, but something like that could be done in a new ticket or as part of #2034.

[jdemeyer]

Replying to tmonteil:

I do not understand the ad-hoc coercion that is made for RealNumber where the precision of self takes predecence over the one of other.

Yes, that was problematic, that is fixed now.

[git]

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

​43eee88

RR __floordiv__: only coerce when needed

[vbraun]

Is there a reason for why we don't fix #2034 first? It seems its a really simple fix in src/sage/structure/element.pyx, just following what is done for __div__. Otherwise whoever wants to tackle that also has to undo the handcrafted type promotion from this ticket.

[jdemeyer]

Replying to vbraun:

Is there a reason for why we don't fix #2034 first?

Not really. Mostly, I don't know how to do it.

[vdelecroix]

I do not agree with your semantic of __floordiv__. Within Sage // is meant for internal division (i.e. quotient of the euclidean division):

sage: x = polygen(ZZ)
sage: p1 = (x+1)*(x+2)
sage: p1 // (x+1)
x + 2
sage: _.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: sage: p1 / (x+1)
x + 2
sage: sage: _.parent()
Fraction Field of Univariate Polynomial Ring in x over Integer Ring

Inside RR or RDF I am not sure what would be the point of //. This is a prefectly valid euclidean division 5 = 2 x 2.5 + 0.

[git]

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

​5e8a5e3	Implement __floordiv__ in the coercion model
​835059f	Remove redundant __floordiv__ from number field elements
​3e0e5b8	Add more doctests for floor division
​3a2fbd1	Merge commit '43eee88a87eb44848b10fac661df963ac829fe3f' into ticket/15260
​616f88c	Use _floordiv_ from the coercion model

[jdemeyer]

Replying to vdelecroix:

I do not agree with your semantic of __floordiv__.

It's consistent with Python's __floordiv__ for float, so this what we should do according to the "principle of least surprise".

[vdelecroix]

Is that what we want

sage: QQ(7) // QQ(3)
2
sage: parent(_)
Integer Ring
sage: RR(7) // RR(3)
2
sage: parent(_)
Integer Ring

Floordiv of two Python floats is a float (in both Python 2 and 3).

[vbraun]

The sage-devel thread is in favor of throwing an exception. Really code shouldn't rely on QQ.__floordiv__ as it is ambiguous and likely to cause difficult-to-see errors.

[bruno]

By the principle of least surprise, I would be in favor of QQ.__floordiv__ behaving the same way as float.__floordiv__ behaves in Python. Another reason for __floordiv__ to be internal is that it gives a generic "exact division" method (division while you know in advance that the result is exact), which has several use cases. For instance if you want to take the primitive part of a polynomial: You can write a generic method which works over fields as well as over rings, as soon as you have a method content which returns 1 for fields and a more interesting content for rings.¹ In a situation where __floordiv__ raises an Exception, you must use a __truediv__ and then convert to the original ring to obtain an exact division.

¹ This example may seem anecdotal though I constantly encounter the need for an exact division. Of course, this is only useful for generic implementation, which could be used with rings or fields.

[jdemeyer]

Replying to bruno:

By the principle of least surprise, I would be in favor of QQ.__floordiv__ behaving the same way as float.__floordiv__ behaves in Python.

In my opinion, QQ and float are very different things so I see no reason why their __floordiv__ methods should be similar.

[jdemeyer]

That being said, I could certainly agree with QQ.__floordiv__ returning a rational which is always an exact integer. That would be:

sage: QQ(7)//QQ(3)
2
sage: parent(QQ(7)//QQ(3))
Rational Field

which looks useful indeed. But I don't know if there is enough consensus for this.

[bruno]

I used QQ as an example, but the same holds for other fields. In the current branch, __floordiv__ always returns an integer, while it should to my mind always be internal. Note that I am strongly against raising an exception since it would be a useless regression. (By this I mean that it would break some existing code, and bring nothing interesting.) I guess that my viewpoint is the same as (close to?) the one expressed by Vincent in comment:28 and comment:30.

Replying to vbraun:

The sage-devel thread is in favor of throwing an exception.

I do not see any such consensus in the sage-devel thread! You are the only one proposing to raise an exception... William says that it is a reasonable option, as is Jeroen's proposal.

[vdelecroix]

See #21745 for modifying only QQ.

Actually I think that a good (partial) specification would be:

• // and % should always be consistent when implemented
• in non-trivial euclidean rings a // b and a % b should stand for the remainder and quotient of euclidean division (eg ZZ, QQ[x]). In these cases, it would just be aliases of a.quo_rem(b)[0] and a.quo_rem(b)[1].
• for subset of the reals it should be the natural extension of integer euclidean division as proposed in ​this thread (see also #21745 and #21747 for a concrete proposal)

[vdelecroix]

Replying to jdemeyer:

That being said, I could certainly agree with QQ.__floordiv__ returning a rational which is always an exact integer. That would be:

sage: QQ(7)//QQ(3)
2
sage: parent(QQ(7)//QQ(3))
Rational Field

which looks useful indeed. But I don't know if there is enough consensus for this.

Would make sense to me and would also be better from the coercion point of view. However in Sage we use to convert exact integer results to integer as in

sage: type((2.5).floor())
<type 'sage.rings.integer.Integer'>

Note that Python is sloppy about the output type

>>> type(2.0 // 1.0)
float
>>> type(fractions.Fraction(2,1) // fractions.Fraction(1,1))
int

(but fractions is not so much a standard)