Floor (integer) division of reals and rationals

[nathanncohen]

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

Depends on #2034

CC: @williamstein @sagetrac-tmonteil @zimmermann6

Component: basic arithmetic

Author: Jan Keitel, Jeroen Demeyer

Branch/Commit: u/jdemeyer/ticket/15260 @ 616f88c

Reviewer: Jeroen Demeyer, Thierry Monteil

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

[sagetrac-tmonteil]

comment:1

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'

[sagetrac-jkeitel]

Author: Jan Keitel

[sagetrac-jkeitel]

comment:4

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.

[sagetrac-jkeitel]

Branch: u/jkeitel/15260

[sagetrac-jkeitel]

Commit: fd78ca5

[jdemeyer]

Changed branch from u/jkeitel/15260 to u/jdemeyer/ticket/15260

[jdemeyer]

Changed commit from fd78ca5 to fc5bca9

[jdemeyer]

New commits:

fc5bca9

RR floordiv: fix rounding

[jdemeyer]

Reviewer: Jeroen Demeyer

[jdemeyer]

comment:8

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

[sagetrac-git]

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

b49487a

Revert generic `__floordiv__`, add `__floordiv__` for rationals

[sagetrac-git]

Changed commit from fc5bca9 to b49487a

[jdemeyer]

comment:10

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

[jdemeyer]

comment:11

Running doctests now...

[jdemeyer]

Changed author from Jan Keitel to Jan Keitel, Jeroen Demeyer

[jdemeyer]

comment:12

Tests passed, needs review.

[sagetrac-tmonteil]

comment:14

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'

[vbraun]

comment:23

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]

comment:24

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.

[videlec]

comment:25

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.

[jdemeyer]

Dependencies: #2034

[sagetrac-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

[sagetrac-git]

Changed commit from 43eee88 to 616f88c

[jdemeyer]

comment:28

Replying to @videlec:

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

[videlec]

comment:30

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]

comment:31

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.

[bgrenet]

comment:32

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]

comment:33

Replying to @bgrenet:

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]

comment:34

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.

[bgrenet]

comment:35

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.

[videlec]

comment:36

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 Standardize modulo operator % on real numbers (step 1) #21745 and Standardize modulo operator % on real numbers (step 2) #21747 for a concrete proposal)

[videlec]

comment:37

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)