Opened 8 years ago

Closed 7 years ago

#11593 closed enhancement (fixed)

`quo_rem` for divisor of leading unit coefficient

Reported by: klee Owned by: AlexGhitza
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)

trac_11593.patch (5.9 KB) - added by klee 7 years ago.
rebased for Sage 5.6

Download all attachments as: .zip

Change History (42)

comment:1 Changed 8 years ago by klee

  • Milestone changed from sage-4.7.2 to sage-4.7.1
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by klee

  • Authors set to Kwankyu Lee

comment:3 Changed 8 years ago by klee

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

  • Status changed from needs_review to needs_info

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

comment:5 follow-up: Changed 8 years ago by klee

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 ; follow-up: Changed 8 years ago by cremona

  • Status changed from needs_info to 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 in reply to: ↑ 6 Changed 8 years ago by klee

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

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

Removing spaces does not help. :-(

comment:10 follow-up: Changed 8 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 8 years ago by klee

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

  • Status changed from needs_review to needs_work
  • Work issues set to 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 7 years ago by klee

  • Dependencies set to #12612
  • Status changed from needs_work to 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:14 Changed 7 years ago by klee

  • Work issues fails doctests deleted

Fixed the doctest failure issues.

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

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.

Last edited 7 years ago by klee (previous) (diff)

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

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 7 years ago by chapoton

  • Status changed from needs_review to positive_review

ok for me, positive review

comment:20 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5
  • Reviewers set to Frédéric Chapoton

comment:21 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.5.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 7 years ago by jdemeyer

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

comment:24 Changed 7 years ago by jdemeyer

  • Resolution fixed deleted
  • Status changed from closed to new

And exceptions should be doctested too.

comment:25 Changed 7 years ago by jdemeyer

  • Merged in sage-5.5.beta1 deleted
  • Status changed from new to needs_review

comment:26 Changed 7 years ago by jdemeyer

  • Keywords fix and doctest exceptions added
  • Status changed from needs_review to needs_work

comment:27 in reply to: ↑ 23 Changed 7 years ago by klee

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 7 years ago by klee

The new patch raises ArithmeticError for nonunit divisor

comment:29 Changed 7 years ago by klee

  • Status changed from needs_work to needs_review

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

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 7 years ago by chapoton

  • Status changed from needs_review to 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 7 years ago by jdemeyer

  • Milestone changed from sage-5.5 to sage-5.6

comment:34 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to 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
**********************************************************************
Last edited 7 years ago by jdemeyer (previous) (diff)

comment:35 Changed 7 years ago by 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 7 years ago by jdemeyer

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 7 years ago by klee

rebased for Sage 5.6

comment:37 Changed 7 years ago by klee

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

comment:38 Changed 7 years ago by klee

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

comment:39 Changed 7 years ago by klee

  • Status changed from needs_work to needs_review

comment:40 Changed 7 years ago by chapoton

  • Status changed from needs_review to positive_review

ok for me, positive review

comment:41 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.8.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.