Opened 8 years ago
Last modified 5 years ago
#15260 needs_info defect
Floor (integer) division of reals and rationals
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  basic arithmetic  Keywords:  
Cc:  was, tmonteil, zimmerma  Merged in:  
Authors:  Jan Keitel, Jeroen Demeyer  Reviewers:  Jeroen Demeyer, Thierry Monteil 
Report Upstream:  N/A  Work issues:  
Branch:  u/jdemeyer/ticket/15260 (Commits, GitHub, GitLab)  Commit:  616f88c009990bd9d778970ac2bb3496e500b1a1 
Dependencies:  #2034  Stopgaps: 
Description (last modified by )
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/sagesupport/xE_S3WbFHzA/discussion [2] https://groups.google.com/d/msg/sagedevel/nQDAMtqnEsY/HfpIdvc9AwAJ
Change History (37)
comment:1 Changed 8 years ago by
comment:2 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 Changed 7 years ago by
 Branch set to u/jkeitel/15260
 Commit set to fd78ca5e31972737b03f29f2703d356e8ea501ab
comment:5 Changed 7 years ago by
 Status changed from new to needs_review
comment:6 Changed 7 years ago by
 Branch changed from u/jkeitel/15260 to u/jdemeyer/ticket/15260
 Created changed from 10/07/13 11:59:20 to 10/07/13 11:59:20
 Modified changed from 08/03/14 06:53:03 to 08/03/14 06:53:03
comment:7 Changed 7 years ago by
 Commit changed from fd78ca5e31972737b03f29f2703d356e8ea501ab to fc5bca925fd378a71eff488a1b3236bfced6d776
 Reviewers set to Jeroen Demeyer
 Summary changed from Integer division of rationals to Integer division of reals and rationals
New commits:
fc5bca9  RR floordiv: fix rounding

comment:8 Changed 7 years ago by
Using the floor()
function for every field is a bad idea, for many fields taking floor()
does not make sense.
comment:9 Changed 7 years ago by
 Commit changed from fc5bca925fd378a71eff488a1b3236bfced6d776 to b49487a1e046a1185d30d2a5694549c60493f951
Branch pushed to git repo; I updated commit sha1. New commits:
b49487a  Revert generic __floordiv__, add __floordiv__ for rationals

comment:10 Changed 7 years ago by
I suggest just making the fixes for reals and rationals and deferring the discussion about a generic __floordiv__
to #2034.
comment:12 Changed 7 years ago by
Tests passed, needs review.
comment:13 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:14 Changed 7 years ago by
 Status changed from needs_review to needs_info
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'
comment:15 Changed 7 years ago by
 Component changed from numerical to basic arithmetic
 Description modified (diff)
 Status changed from needs_info to needs_work
comment:16 Changed 7 years ago by
 Commit changed from b49487a1e046a1185d30d2a5694549c60493f951 to a7dde8bebc558d4f3a7cff9f6c26dab40e2ec55b
Branch pushed to git repo; I updated commit sha1. New commits:
a7dde8b  Add __floordiv__ for RDF and RIF

comment:17 Changed 7 years ago by
 Modified changed from 08/13/14 07:48:09 to 08/13/14 07:48:09
 Status changed from needs_work to needs_review
comment:18 followups: ↓ 19 ↓ 20 Changed 7 years ago by
 Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Thierry Monteil
 Status changed from needs_review to needs_info
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 adhoc 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 ?
comment:19 in reply to: ↑ 18 Changed 7 years ago by
 Status changed from needs_info to needs_work
Replying to tmonteil:
The condition
if not other != 0:
looks weird. For real interval fields, why not usingother.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 aNotImplementedError
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.
comment:20 in reply to: ↑ 18 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to tmonteil:
I do not understand the adhoc coercion that is made for
RealNumber
where the precision ofself
takes predecence over the one ofother
.
Yes, that was problematic, that is fixed now.
comment:21 Changed 7 years ago by
 Commit changed from a7dde8bebc558d4f3a7cff9f6c26dab40e2ec55b to 43eee88a87eb44848b10fac661df963ac829fe3f
Branch pushed to git repo; I updated commit sha1. New commits:
43eee88  RR __floordiv__: only coerce when needed

comment:22 Changed 7 years ago by
 Summary changed from Integer division of reals and rationals to Floor (integer) division of reals and rationals
comment:23 followup: ↓ 24 Changed 7 years ago by
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.
comment:24 in reply to: ↑ 23 Changed 7 years ago by
comment:25 followup: ↓ 28 Changed 6 years ago by
 Status changed from needs_review to needs_info
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
.
comment:26 Changed 5 years ago by
 Dependencies set to #2034
 Milestone changed from sage6.4 to sage7.1
 Status changed from needs_info to needs_work
comment:27 Changed 5 years ago by
 Commit changed from 43eee88a87eb44848b10fac661df963ac829fe3f to 616f88c009990bd9d778970ac2bb3496e500b1a1
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

comment:28 in reply to: ↑ 25 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
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".
comment:29 Changed 5 years ago by
 Cc was added; wstein removed
comment:30 Changed 5 years ago by
 Status changed from needs_review to needs_info
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).
comment:31 followup: ↓ 35 Changed 5 years ago by
The sagedevel thread is in favor of throwing an exception. Really code shouldn't rely on QQ.__floordiv__
as it is ambiguous and likely to cause difficulttosee errors.
comment:32 followup: ↓ 33 Changed 5 years ago by
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.
comment:33 in reply to: ↑ 32 Changed 5 years ago by
Replying to bruno:
By the principle of least surprise, I would be in favor of
QQ.__floordiv__
behaving the same way asfloat.__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.
comment:34 followup: ↓ 37 Changed 5 years ago by
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.
comment:35 in reply to: ↑ 31 Changed 5 years ago by
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 sagedevel thread is in favor of throwing an exception.
I do not see any such consensus in the sagedevel thread! You are the only one proposing to raise an exception... William says that it is a reasonable option, as is Jeroen's proposal.
comment:36 Changed 5 years ago by
See #21745 for modifying only QQ.
Actually I think that a good (partial) specification would be:
//
and%
should always be consistent when implemented in nontrivial euclidean rings
a // b
anda % b
should stand for the remainder and quotient of euclidean division (egZZ
,QQ[x]
). In these cases, it would just be aliases ofa.quo_rem(b)[0]
anda.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)
comment:37 in reply to: ↑ 34 Changed 5 years ago by
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 Fieldwhich 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)
The reason is that for rationals (and apparently more generally for
FieldElement
), we havewhere it should be
I will do a patch once i have compiled a more recent version of Sage
What is fun is that