Opened 9 years ago

Last modified 6 years ago

# Floor (integer) division of reals and rationals

Reported by: Owned by: ncohen major sage-7.1 basic arithmetic was, tmonteil, zimmerma Jan Keitel, Jeroen Demeyer Jeroen Demeyer, Thierry Monteil N/A u/jdemeyer/ticket/15260 616f88c009990bd9d778970ac2bb3496e500b1a1 #2034

### 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
```

### comment:1 Changed 9 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 9 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:3 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:4 Changed 8 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:

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

### comment:5 Changed 8 years ago by jkeitel

• Status changed from new to needs_review

### comment:6 Changed 8 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 8 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:

 ​fc5bca9 `RR floordiv: fix rounding`

### comment:8 Changed 8 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 8 years ago by git

• 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 8 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 8 years ago by jdemeyer

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

Running doctests now...

### comment:12 Changed 8 years ago by jdemeyer

Tests passed, needs review.

### comment:13 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:14 Changed 8 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 8 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 8 years ago by git

• 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 8 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: ↓ 19 ↓ 20 Changed 8 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 8 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 8 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 8 years ago by git

• 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 8 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: ↓ 24 Changed 8 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 8 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: ↓ 28 Changed 7 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 7 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 7 years ago by git

• 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 7 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 7 years ago by jdemeyer

• Cc was added; wstein removed

### comment:30 Changed 7 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: ↓ 35 Changed 7 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: ↓ 33 Changed 6 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 6 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: ↓ 37 Changed 6 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 6 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 6 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 6 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.