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:

Status badges

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)

trac_11593.patch (5.9 KB) - added by Kwankyu Lee 10 years ago.
rebased for Sage 5.6

Download all attachments as: .zip

Change History (42)

comment:1 Changed 11 years ago by Kwankyu Lee

Milestone: sage-4.7.2sage-4.7.1
Status: newneeds_review

comment:2 Changed 11 years ago by Kwankyu Lee

Authors: Kwankyu Lee

comment:3 Changed 11 years ago by Kwankyu Lee

The patch allows one to compute the quotient and the remainder for divisors of unit leading coefficient. The quo_rem added to Polynomial_generic_dense is slightly faster than quo_rem defined in Polynomial_generic_field.

comment:4 Changed 11 years ago by John Cremona

Status: needs_reviewneeds_info

In the case where self is 0 should it not be self, other returned? Not self, self?

comment:5 Changed 11 years ago by Kwankyu Lee

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 in reply to:  5 ; Changed 11 years ago by John Cremona

Status: needs_infoneeds_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 in reply to:  6 Changed 11 years ago by Kwankyu Lee

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 Kwankyu Lee

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:9 Changed 11 years ago by Kwankyu Lee

Removing spaces does not help. :-(

comment:10 Changed 11 years ago by aapitzsch

Looking forward to Python3, use the "new" syntax to raise errors, i.e.

raise ZeroDivisionError("division by zero polynomial")

comment:11 in reply to:  10 Changed 11 years ago by Kwankyu Lee

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 David Loeffler

Status: needs_reviewneeds_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 Kwankyu Lee

Dependencies: #12612
Status: needs_workneeds_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:14 Changed 10 years ago by Kwankyu Lee

Work issues: fails doctests

Fixed the doctest failure issues.

comment:15 Changed 10 years ago by Frédéric 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.

comment:16 in reply to:  15 Changed 10 years ago by Kwankyu Lee

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

Version 0, edited 10 years ago by Kwankyu Lee (next)

comment:17 Changed 10 years ago by Frédéric 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..

comment:18 in reply to:  17 Changed 10 years ago by Kwankyu Lee

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 Frédéric Chapoton

Status: needs_reviewpositive_review

ok for me, positive review

comment:20 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.4sage-5.5
Reviewers: Frédéric Chapoton

comment:21 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.5.beta1
Resolution: fixed
Status: positive_reviewclosed

comment:22 Changed 10 years ago by Jeroen Demeyer

sage-5.5.beta0 + #11593 gives

sage -t --long "devel/sage/sage/schemes/elliptic_curves/ell_number_field.py"
The doctested process was killed by signal 11
         [166.4 s]

on OS X 10.4 PPC (not on other systems as far as I know).

I think the real issue is with #715+#11521, not this ticket.

comment:23 Changed 10 years ago by Jeroen Demeyer

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 Jeroen Demeyer

Resolution: fixed
Status: closednew

And exceptions should be doctested too.

comment:25 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.5.beta1
Status: newneeds_review

comment:26 Changed 10 years ago by Jeroen Demeyer

Keywords: fix and doctest exceptions added
Status: needs_reviewneeds_work

comment:27 in reply to:  23 Changed 10 years ago by Kwankyu Lee

Replying to jdemeyer:

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.

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:28 Changed 10 years ago by Kwankyu Lee

The new patch raises ArithmeticError for nonunit divisor

comment:29 Changed 10 years ago by Kwankyu Lee

Status: needs_workneeds_review

comment:30 Changed 10 years ago by Frédéric 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 ?

comment:31 in reply to:  30 Changed 10 years ago by Kwankyu Lee

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 Frédéric Chapoton

Status: needs_reviewpositive_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 Jeroen Demeyer

Milestone: sage-5.5sage-5.6

comment:34 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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
**********************************************************************
Last edited 10 years ago by Jeroen Demeyer (previous) (diff)

comment:35 Changed 10 years ago by Frédéric Chapoton

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 Jeroen Demeyer

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.

Changed 10 years ago by Kwankyu Lee

Attachment: trac_11593.patch added

rebased for Sage 5.6

comment:37 Changed 10 years ago by Kwankyu Lee

Actually the fault was with #8992. There is now no need to take off the problematic doctest of #8992.

comment:38 Changed 10 years ago by Kwankyu Lee

The faulty part of #8992 is now remedied and included in the current patch for this ticket.

comment:39 Changed 10 years ago by Kwankyu Lee

Status: needs_workneeds_review

comment:40 Changed 10 years ago by Frédéric Chapoton

Status: needs_reviewpositive_review

ok for me, positive review

comment:41 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.8.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.