Opened 11 years ago
Closed 10 years ago
#11593 closed enhancement (fixed)
`quo_rem` for divisor of leading unit coefficient
Reported by: | Kwankyu Lee | Owned by: | Alex Ghitza |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.8 |
Component: | basic arithmetic | Keywords: | fix and doctest exceptions |
Cc: | Merged in: | sage-5.8.beta2 | |
Authors: | Kwankyu Lee | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12612 | Stopgaps: |
Description
quo_rem
does not work for divisors of unit leading coefficients, though the quotient and the remainder are defined mathematically.
sage: R.<y> = QQ[x][] sage: f = R.random_element(200) sage: g = y^100+R.random_element(99) sage: q, r = f.quo_rem(g) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) ... AttributeError: 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense' object has no attribute 'quo_rem'
Attachments (1)
Change History (42)
comment:1 Changed 11 years ago by
Milestone: | sage-4.7.2 → sage-4.7.1 |
---|---|
Status: | new → needs_review |
comment:2 Changed 11 years ago by
Authors: | → Kwankyu Lee |
---|
comment:3 Changed 11 years ago by
comment:4 Changed 11 years ago by
Status: | needs_review → needs_info |
---|
In the case where self is 0 should it not be self, other returned? Not self, self?
comment:5 follow-up: 6 Changed 11 years ago by
The quotient and the remainder of 0(=self) divided by other is 0 and 0. So self, self is correct.
By the way, I did not care for this patch for a while. It needs to be rebased for the current Sage beta. I can't do it right away. I would appreciate if you do it.
comment:6 follow-up: 7 Changed 11 years ago by
Status: | needs_info → needs_review |
---|
Replying to klee:
The quotient and the remainder of 0(=self) divided by other is 0 and 0. So self, self is correct.
OK, I was being stupid.
By the way, I did not care for this patch for a while. It needs to be rebased for the current Sage beta. I can't do it right away. I would appreciate if you do it.
Well, I have many other things to do -- especially as at present I am running Sage Days 35.
comment:7 Changed 11 years ago by
Replying to cremona:
Well, I have many other things to do -- especially as at present I am running Sage Days 35.
Sorry for the suggestion. You are now the busiest man in the Sage community. :-) Good wish for Sage Days 35.
comment:8 Changed 11 years ago by
I see no doctest failures on my own Ubuntu 11.10 and Mac. I don't know what to do with the patchbot results.
comment:10 follow-up: 11 Changed 11 years ago by
Looking forward to Python3, use the "new" syntax to raise errors, i.e.
raise ZeroDivisionError("division by zero polynomial")
comment:11 Changed 11 years ago by
Replying to aapitzsch:
Looking forward to Python3, use the "new" syntax to raise errors, i.e.
raise ZeroDivisionError("division by zero polynomial")
Done.
comment:12 Changed 11 years ago by
Status: | needs_review → needs_work |
---|---|
Work issues: | → fails doctests |
According to the patchbot, some doctests are fail with this patch on the current beta (5.0.beta8):
sage -t -force_lib devel/sage-11593/sage/rings/function_field/function_field_element.pyx ********************************************************************** File "/storage/masiao/sage-5.0.beta8-patchbot/devel/sage-11593/sage/rings/function_field/function_field_element.pyx", line 423: sage: a = ~(2*y + 1/x); a # indirect doctest Expected: (-x^2/(8*x^5 + x^2 + 1/2))*y + (2*x^3 + x)/(16*x^5 + 2*x^2 + 1) Got: (-1/2*x^2/(4*x^5 + 1/2*x^2 + 1/4))*y + (1/2*x^3 + 1/4*x)/(4*x^5 + 1/2*x^2 + 1/4) ********************************************************************** File "/storage/masiao/sage-5.0.beta8-patchbot/devel/sage-11593/sage/rings/function_field/function_field_element.pyx", line 443: sage: a = ~(2*y + 1/x); a Expected: (-x^2/(8*x^5 + x^2 + 1/2))*y + (2*x^3 + x)/(16*x^5 + 2*x^2 + 1) Got: (-1/2*x^2/(4*x^5 + 1/2*x^2 + 1/4))*y + (1/2*x^3 + 1/4*x)/(4*x^5 + 1/2*x^2 + 1/4) ********************************************************************** File "/storage/masiao/sage-5.0.beta8-patchbot/devel/sage-11593/sage/rings/function_field/function_field_element.pyx", line 445: sage: a.list() Expected: [(2*x^3 + x)/(16*x^5 + 2*x^2 + 1), -x^2/(8*x^5 + x^2 + 1/2)] Got: [(1/2*x^3 + 1/4*x)/(4*x^5 + 1/2*x^2 + 1/4), -1/2*x^2/(4*x^5 + 1/2*x^2 + 1/4)] **********************************************************************
comment:13 Changed 10 years ago by
Dependencies: | → #12612 |
---|---|
Status: | needs_work → needs_review |
The new code also speeds up things. See below
Before the patch,
sage: sage: S.<x>=QQ[] sage: sage: fS=FractionField(S) sage: sage: R.<y>=fS[] sage: sage: f=y^20 sage: sage: g=y^5+1/x*y^4 sage: sage: timeit("f.quo_rem(g)") 125 loops, best of 3: 3.25 ms per loop
After the patch,
sage: sage: S.<x>=QQ[] sage: sage: fS=FractionField(S) sage: sage: R.<y>=fS[] sage: sage: f=y^20 sage: sage: g=y^5+1/x*y^4 sage: sage: timeit("f.quo_rem(g)") 125 loops, best of 3: 1.75 ms per loop
comment:15 follow-up: 16 Changed 10 years ago by
Maybe one could consider adding documentation for the procedure cdef _inplace_truncate ?
You are changing something inside this procedure, so the correct behaviour should be tested.
comment:16 Changed 10 years ago by
Replying to chapoton:
Maybe one could consider adding documentation for the procedure cdef _inplace_truncate ?
You are changing something inside this procedure, so the correct behaviour should be tested.
I corrected a bug in _inplace_truncate, which is of only internal use, unlike the truncate method defined just above it. It's correct behaviour is indirectly checked by other methods that use it in various places. On the other hand, the procedure is quite self-explanatory by its name and the short code, and I doubt the value of a documentation for it.
comment:17 follow-up: 18 Changed 10 years ago by
Well, I understand. But it would have been one little step towards the official goal of 100% doctesting. The question is not so much the value of the documentation, that its mere existence, even if it is not very useful..
comment:18 Changed 10 years ago by
Replying to chapoton:
Well, I understand. But it would have been one little step towards the official goal of 100% doctesting. The question is not so much the value of the documentation, that its mere existence, even if it is not very useful..
I found out that as _inplace_truncate
is only a cdef
method, that is not even counted for the doctest coverage. See the result of
sage -coverage sage/rings/polynomial/polynomial_element.pyx
comment:19 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
ok for me, positive review
comment:20 Changed 10 years ago by
Milestone: | sage-5.4 → sage-5.5 |
---|---|
Reviewers: | → Frédéric Chapoton |
comment:21 Changed 10 years ago by
Merged in: | → sage-5.5.beta1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:22 Changed 10 years ago by
comment:23 follow-up: 27 Changed 10 years ago by
Besides, why TypeError
when dividing by a non-unit? It seems to me that TypeError
is not the right exception for this, I believe ArithmeticError
suits better.
comment:24 Changed 10 years ago by
Resolution: | fixed |
---|---|
Status: | closed → new |
And exceptions should be doctested too.
comment:25 Changed 10 years ago by
Merged in: | sage-5.5.beta1 |
---|---|
Status: | new → needs_review |
comment:26 Changed 10 years ago by
Keywords: | fix and doctest exceptions added |
---|---|
Status: | needs_review → needs_work |
comment:27 Changed 10 years ago by
Replying to jdemeyer:
Besides, why
TypeError
when dividing by a non-unit? It seems to me thatTypeError
is not the right exception for this, I believeArithmeticError
suits better.
TypeError
was my inevitable choice to avoid triggering doctest failures in other parts of Sage, which depend on TypeError
exception for normal operation. I need to remind myself of the details how and where that happens.
comment:29 Changed 10 years ago by
Status: | needs_work → needs_review |
---|
comment:30 follow-up: 31 Changed 10 years ago by
maybe the second and third tests at the beginning should rather be swapped ? What do we expect when we divide 0 by something which does not have an invertible leading coefficient ?
comment:31 Changed 10 years ago by
Replying to chapoton:
maybe the second and third tests at the beginning should rather be swapped ? What do we expect when we divide 0 by something which does not have an invertible leading coefficient ?
Good point! The tests are swapped in a new patch.
comment:32 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
well, let me give again a positive review. Maybe the long-test problem is still there, but it does not appear on 5.4rc3.
comment:33 Changed 10 years ago by
Milestone: | sage-5.5 → sage-5.6 |
---|
comment:34 Changed 10 years ago by
Status: | positive_review → needs_work |
---|
With #8992, I get
********************************************************************** File "/release/merger/sage-5.6.beta0/devel/sage-main/sage/rings/polynomial/polynomial_quotient_ring.py", line 407: sage: Q3(Q1.gen()) Exception raised: Traceback (most recent call last): File "/release/merger/sage-5.6.beta0/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/release/merger/sage-5.6.beta0/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/release/merger/sage-5.6.beta0/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_5[28]>", line 1, in <module> Q3(Q1.gen())###line 407: sage: Q3(Q1.gen()) File "parent.pyx", line 800, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7268) File "parent.pyx", line 2153, in sage.structure.parent.Parent.convert_map_from (sage/structure/parent.c:15082) File "parent.pyx", line 2165, in sage.structure.parent.Parent.discover_convert_map_from (sage/structure/parent.c:15301) File "parent.pyx", line 1903, in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:14051) File "parent.pyx", line 1974, in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:13804) File "parent.pyx", line 2068, in sage.structure.parent.Parent.discover_coerce_map_from (sage/structure/parent.c:14231) File "parent_old.pyx", line 507, in sage.structure.parent_old.Parent._coerce_map_from_ (sage/structure/parent_old.c:6428) File "/release/merger/sage-5.6.beta0/local/lib/python/site-packages/sage/rings/polynomial/polynomial_quotient_ring.py", line 485, in _coerce_map_from_ if not self.__polynomial.divides(R.modulus()): File "element.pyx", line 2027, in sage.structure.element.CommutativeRingElement.divides (sage/structure/element.c:16725) File "element.pyx", line 2021, in sage.structure.element.CommutativeRingElement.divides (sage/structure/element.c:16636) File "polynomial_element.pyx", line 1724, in sage.rings.polynomial.polynomial_element.Polynomial.__mod__ (sage/rings/polynomial/polynomial_element.c:16751) _, R = self.quo_rem(other) File "element.pyx", line 3223, in sage.structure.element.NamedBinopMethod.__call__ (sage/structure/element.c:24763) File "polynomial_element.pyx", line 6478, in sage.rings.polynomial.polynomial_element.Polynomial_generic_dense.quo_rem (sage/rings/polynomial/polynomial_element.c:47106) raise ArithmeticError("Nonunit leading coefficient") ArithmeticError: Nonunit leading coefficient **********************************************************************
I don't know whether the fault lies with #8992 or with #11593.
comment:35 Changed 10 years ago by
Well, this failing test does not make sense to me. Why on earth should we be able to convert
x as element of the ring Q[x]/(x^6 - x^4 - 5*x^2 - 3) to x as element of the ring Q[x][y]/(y^2+1)
I propose to remove this test. Anybody else has an opinion ?
comment:36 Changed 10 years ago by
I think the doctest explains it pretty well: it is a conversion from Q[x]/(x^6 - x^4 - 5*x^2 - 3)
to Q[x]
which matters.
You can ask questions at #8992, where this test was introduced.
comment:37 Changed 10 years ago by
comment:38 Changed 10 years ago by
The faulty part of #8992 is now remedied and included in the current patch for this ticket.
comment:39 Changed 10 years ago by
Status: | needs_work → needs_review |
---|
comment:40 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
ok for me, positive review
comment:41 Changed 10 years ago by
Merged in: | → sage-5.8.beta2 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
The patch allows one to compute the quotient and the remainder for divisors of unit leading coefficient. The
quo_rem
added toPolynomial_generic_dense
is slightly faster thanquo_rem
defined inPolynomial_generic_field
.