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

Status badges

Description (last modified by jdemeyer)

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

Change History (37)

comment:1 Changed 8 years ago by 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'

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by jkeitel

  • Authors set to Jan Keitel
  • Branch set to u/jkeitel/15260
  • Commit set to fd78ca5e31972737b03f29f2703d356e8ea501ab

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


New commits:

c9146beFix floordiv of FieldElements.
fd78ca5Floordiv for real_mpfr.

comment:5 Changed 7 years ago by jkeitel

  • Status changed from new to needs_review

comment:6 Changed 7 years ago by jdemeyer

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

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

fc5bca9RR floordiv: fix rounding

comment:8 Changed 7 years ago by jdemeyer

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 git

  • Commit changed from fc5bca925fd378a71eff488a1b3236bfced6d776 to b49487a1e046a1185d30d2a5694549c60493f951

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

b49487aRevert generic __floordiv__, add __floordiv__ for rationals

comment:10 Changed 7 years ago by jdemeyer

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

comment:11 Changed 7 years ago by jdemeyer

  • Authors changed from Jan Keitel to Jan Keitel, Jeroen Demeyer

Running doctests now...

comment:12 Changed 7 years ago by jdemeyer

Tests passed, needs review.

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:14 Changed 7 years ago by tmonteil

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

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

  • Commit changed from b49487a1e046a1185d30d2a5694549c60493f951 to a7dde8bebc558d4f3a7cff9f6c26dab40e2ec55b

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

a7dde8bAdd __floordiv__ for RDF and RIF

comment:17 Changed 7 years ago by jdemeyer

  • 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 follow-ups: Changed 7 years ago by tmonteil

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

comment:19 in reply to: ↑ 18 Changed 7 years ago by jdemeyer

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

comment:20 in reply to: ↑ 18 Changed 7 years ago by jdemeyer

  • Status changed from needs_work to needs_review

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.

comment:21 Changed 7 years ago by git

  • Commit changed from a7dde8bebc558d4f3a7cff9f6c26dab40e2ec55b to 43eee88a87eb44848b10fac661df963ac829fe3f

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

43eee88RR __floordiv__: only coerce when needed

comment:22 Changed 7 years ago by jdemeyer

  • Summary changed from Integer division of reals and rationals to Floor (integer) division of reals and rationals

comment:23 follow-up: Changed 7 years ago by 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.

comment:24 in reply to: ↑ 23 Changed 7 years ago by 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.

comment:25 follow-up: Changed 6 years ago by vdelecroix

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

  • Dependencies set to #2034
  • Milestone changed from sage-6.4 to sage-7.1
  • Status changed from needs_info to needs_work

comment:27 Changed 5 years ago by git

  • Commit changed from 43eee88a87eb44848b10fac661df963ac829fe3f to 616f88c009990bd9d778970ac2bb3496e500b1a1

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

5e8a5e3Implement __floordiv__ in the coercion model
835059fRemove redundant __floordiv__ from number field elements
3e0e5b8Add more doctests for floor division
3a2fbd1Merge commit '43eee88a87eb44848b10fac661df963ac829fe3f' into ticket/15260
616f88cUse _floordiv_ from the coercion model

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

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

  • Cc was added; wstein removed

comment:30 Changed 5 years ago by vdelecroix

  • 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 follow-up: Changed 5 years ago by 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.

comment:32 follow-up: Changed 5 years ago by 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.

comment:33 in reply to: ↑ 32 Changed 5 years ago by 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.

comment:34 follow-up: Changed 5 years ago by 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.

comment:35 in reply to: ↑ 31 Changed 5 years ago by 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.

comment:36 Changed 5 years ago by 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)

comment:37 in reply to: ↑ 34 Changed 5 years ago by 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)

Note: See TracTickets for help on using tickets.