#26907 closed defect (fixed)

Exact division in ℤ[x][y] is broken

Reported by: mmezzarobba Owned by:
Priority: critical Milestone: sage-8.7
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Travis Scrimshaw, Marc Mezzarobba Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 839c605 (Commits) Commit: 839c605a6160d26877b184958a307cf42ffe21f9
Dependencies: Stopgaps:

Description (last modified by mmezzarobba)

Issue:

sage: P.<x> = ZZ[]
sage: Q.<y> = P[]
sage: a = 3*y + 1
sage: a//a
TypeError: no conversion of this rational to integer

due to cb8db697a1b (#26433).

The branch on this ticket fixes that issue and improves inverse_of_unit(); see the commit messages for detail.

Change History (21)

comment:1 Changed 23 months ago by tscrim

The simple fix should be to add

         try:
             inv = y[n-1].inverse_of_unit()
-        except (ArithmeticError, ValueError):
+        except (ArithmeticError, ValueError, TypeError):
             inv = ~(y[n-1])
             convert = True

However, I would argue the real bug is here:

sage: R.<x> = ZZ[]
sage: R(2).inverse_of_unit()
...
TypeError: no conversion of this rational to integer

In particular, we are inconsistent about the type of error that is raised. This was an assumption in the code block above, which is why it was not caught. Hence, the above change should fix this, but sweep the underlying issue under the rug.

Also, wouldn't it be better to do

         elif d == -1:
             return self._parent(~self._parent._base.zero())
-        return self._parent(~self.get_unsafe(0))
+        return self._parent(self.get_unsafe(0).inverse_of_unit())

Side note: We probably should add a generic inverse_of_unit to the category of Fields that simply returns ~self.

Last edited 23 months ago by tscrim (previous) (diff)

comment:2 Changed 22 months ago by mmezzarobba

  • Authors set to Travis Scrimshaw, Marc Mezzarobba
  • Branch set to u/mmezzarobba/poly_inverse_of_unit
  • Commit set to 9f94bd6056d8f62dd1a417fc8aac65a653b51322
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

238c1b7#26907 Polynomial.inverse_of_unit(): fix choice of exception
30831ce#26907 check that exact division in ℤ[x][y] works again
9f94bd6Fields: generic inverse_of_unit()

comment:3 follow-up: Changed 22 months ago by tscrim

So this behavior should change now with this change:

sage: RR(0).inverse_of_unit()
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-7-9817ebd4dc31> in <module>()
----> 1 RR(Integer(0)).inverse_of_unit()

/home/travis/sage-build/local/lib/python2.7/site-packages/sage/categories/rings.pyc in inverse_of_unit(self)
   1155             try:
   1156                 if not self.is_unit():
-> 1157                     raise ArithmeticError("element is not a unit")
   1158             except NotImplementedError:
   1159                 # if an element does not implement is_unit, we just try to

ArithmeticError: element is not a unit
sage: 1/RR(0)
+infinity

I think it is the correct change, but I am now maybe a little worried about assumptions and we might want to quickly ask on sage-devel about this to confirm.

Also, a better test:

                sage: try:
                ....:    QQ(0).inverse_of_unit()
                ....: except ArithmeticError as e:
                ....:    print(type(e))
                <... 'exceptions.ZeroDivisionError'>

to

                sage: QQ(0).inverse_of_unit()
                Traceback (most recent call last):
                ...
                ZeroDivisionError: rational division by zero

comment:4 in reply to: ↑ 3 Changed 22 months ago by mmezzarobba

Replying to tscrim:

So this behavior should change now with this change:

sage: RR(0).inverse_of_unit()
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-7-9817ebd4dc31> in <module>()
----> 1 RR(Integer(0)).inverse_of_unit()

/home/travis/sage-build/local/lib/python2.7/site-packages/sage/categories/rings.pyc in inverse_of_unit(self)
   1155             try:
   1156                 if not self.is_unit():
-> 1157                     raise ArithmeticError("element is not a unit")
   1158             except NotImplementedError:
   1159                 # if an element does not implement is_unit, we just try to

ArithmeticError: element is not a unit
sage: 1/RR(0)
+infinity

I think it is the correct change, but I am now maybe a little worried about assumptions and we might want to quickly ask on sage-devel about this to confirm.

I just followed your suggestion here, I have no opinion on the matter.

Also, a better test:

                sage: try:
                ....:    QQ(0).inverse_of_unit()
                ....: except ArithmeticError as e:
                ....:    print(type(e))
                <... 'exceptions.ZeroDivisionError'>

to

                sage: QQ(0).inverse_of_unit()
                Traceback (most recent call last):
                ...
                ZeroDivisionError: rational division by zero

I deliberately wrote it that way, to hint to the fact that it is often better to catch all ArithmeticErrors than just ZeroDivisionErrors if you are calling inverse_of_unit()—but yes, I should have been more explicit!

comment:5 Changed 22 months ago by git

  • Commit changed from 9f94bd6056d8f62dd1a417fc8aac65a653b51322 to 40ab0ae49a429836f8c85275b6082f02e6863563

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

40ab0aeFields: generic inverse_of_unit()

comment:6 Changed 22 months ago by git

  • Commit changed from 40ab0ae49a429836f8c85275b6082f02e6863563 to 323cc39bc0b47bbfe954faf57182887681f472f6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0601737#26907 Polynomial.inverse_of_unit(): fix choice of exception
c2230a2#26907 check that exact division in ℤ[x][y] works again
323cc39Fields: generic inverse_of_unit()

comment:7 Changed 22 months ago by mmezzarobba

  • Milestone changed from sage-8.5 to sage-8.6
  • Priority changed from major to critical

Critical is perhaps a bit strong, but it would be nice if this branch could go in 8.6, since it fixes a regression introduced in 8.5.

comment:8 follow-up: Changed 22 months ago by vdelecroix

The following works without any patch

sage: NumberField(x^7+2,'a')(2).inverse_of_unit()
1/2

comment:9 follow-up: Changed 22 months ago by vdelecroix

Why do you try/catch here

+        try:
+            inv = cst.inverse_of_unit()
+        except (TypeError, ValueError):
+            raise ArithmeticError(f"{self} is not a unit in {self.parent()}")

The error generated by calling inverse_of_unit should just be fine.

comment:10 in reply to: ↑ 8 Changed 22 months ago by mmezzarobba

Replying to vdelecroix:

The following works without any patch

sage: NumberField(x^7+2,'a')(2).inverse_of_unit()
1/2

That's expected. The part that fixes the bug is in the first two commits; the third is general cleanup suggested by Travis above.

Last edited 22 months ago by mmezzarobba (previous) (diff)

comment:11 in reply to: ↑ 9 ; follow-up: Changed 22 months ago by mmezzarobba

Replying to vdelecroix:

Why do you try/catch here

+        try:
+            inv = cst.inverse_of_unit()
+        except (TypeError, ValueError):
+            raise ArithmeticError(f"{self} is not a unit in {self.parent()}")

The error generated by calling inverse_of_unit should just be fine.

Because // now relies on the exception being ArithmeticError (that's what caused of the regression, and the convention used by inverse_of_unit() elsewhere in Sage). While I fixed inverse_of_unit() in the case that caused the issue reported in this ticket, there may be other code paths that raise the wrong exception.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 22 months ago by vdelecroix

Replying to mmezzarobba:

Replying to vdelecroix:

Why do you try/catch here

+        try:
+            inv = cst.inverse_of_unit()
+        except (TypeError, ValueError):
+            raise ArithmeticError(f"{self} is not a unit in {self.parent()}")

The error generated by calling inverse_of_unit should just be fine.

Because // now relies on the exception being ArithmeticError (that's what caused of the regression, and the convention used by inverse_of_unit() elsewhere in Sage). While I fixed inverse_of_unit() in the case that caused the issue reported in this ticket, there may be other code paths that raise the wrong exception.

If any, it would be better to fix the error in inverse of unit rather than introducing this workaround that hides the problem.

comment:13 Changed 22 months ago by vdelecroix

Since you seriously modified inverse_of_unit, you should update the ticket description.

comment:14 in reply to: ↑ 12 ; follow-up: Changed 22 months ago by mmezzarobba

  • Description modified (diff)

Replying to vdelecroix:

If any, it would be better to fix the error in inverse of unit rather than introducing this workaround that hides the problem.

I don't think so. Raising another exception is a really minor issue compared to breaking mathematical functionality; and, since it will typically come from conversion failures, it might even be a reasonable choice in some cases.

Replying to vdelecroix:

Since you seriously modified inverse_of_unit, you should update the ticket description.

Done, though IMO people really should stop confusing ticket descriptions and commit messages...

comment:15 in reply to: ↑ 14 ; follow-up: Changed 22 months ago by tscrim

Replying to mmezzarobba:

Replying to vdelecroix:

If any, it would be better to fix the error in inverse of unit rather than introducing this workaround that hides the problem.

I don't think so. Raising another exception is a really minor issue compared to breaking mathematical functionality; and, since it will typically come from conversion failures, it might even be a reasonable choice in some cases.

I agree with Vincent here as consistent error messages are not only better practice, but are also useful. It allows a TypeError raised from actual bug to be percolated up instead of being caught and maybe silently working.

comment:16 Changed 22 months ago by git

  • Commit changed from 323cc39bc0b47bbfe954faf57182887681f472f6 to 839c605a6160d26877b184958a307cf42ffe21f9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d5a76c4#26907 Polynomial.inverse_of_unit(): fix choice of exception
f2d3561#26907 check that exact division in ℤ[x][y] works again
839c605#26907 Fields: generic inverse_of_unit()

comment:17 in reply to: ↑ 15 Changed 22 months ago by mmezzarobba

Replying to tscrim:

I agree with Vincent here as consistent error messages are not only better practice, but are also useful. It allows a TypeError raised from actual bug to be percolated up instead of being caught and maybe silently working.

I really don't follow your reasoning, but if that's what it takes to get the issue fixed, so be it.

comment:18 Changed 22 months ago by mmezzarobba

The test failure in polyhedron/library.py seems unrelated (and doesn't occur on my box).

comment:19 Changed 22 months ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Ok for me. Merci Marc.

comment:20 Changed 22 months ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:21 Changed 21 months ago by vbraun

  • Branch changed from u/mmezzarobba/poly_inverse_of_unit to 839c605a6160d26877b184958a307cf42ffe21f9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.