Make `quo_rem` give answers more often

[bgrenet]

In generic implementations of f.quo_rem(g), an exception

ArithmeticError: Nonunit leading coefficient

is raised as soon as the leading coefficient of g is not invertible. This was introduced by ticket #11593, and I mimicked the behavior in #16544.

The change I propose is to try to compute the Euclidean division, and raise an exception

ArithmeticError: division not exact (consider coercing to polynomials over the fraction field first)

when the computation is not possible. Then, quo_rem would produce less exceptions, and in particular give an answer each time the answer is not controversial (see below).

Note on the controverse. There is a debate to know whether one should raise an exception when the division is not exact (as it is done for dense integer polynomials with the NTL implementation), or if one should silently return a result that has a mathematical meaning though it is not a Euclidean division (as it is done with the flint implementation). See #16276 as well as https://groups.google.com/d/msg/sage-devel/UVrx5CG4qA0/WUz2RItJtF8J for this debate. My proposition is to already implement a more capable algorithm, and not to wait for the debate to be closed.

Component: basic arithmetic

Keywords: quo_rem

Author: Bruno Grenet

Branch/Commit: dbfb518

Reviewer: Frédéric Chapoton, Ralf Stephan

Issue created by migration from https://trac.sagemath.org/ticket/16649

[bgrenet]

comment:1

My proposition is as follows (say for the method quo_rem of the class Polynomial_generic_dense):

• Remove the test

          if not other.leading_coefficient().is_unit():
              raise ArithmeticError("Nonunit leading coefficient")

  on lines 7484-7485 of sage/rings/polynomial/polynomial_element.pyx.

• Change the line 7999 (q = x[n+k-1]/y[n-1]) by the following:

              try:
                  q = R(x[n+k-1]/y[n-1])
              except TypeError:
                  raise ArithmeticError("Division not exact (consider coercing to polynomial over the fraction field first")

Does the change make sense?

[bgrenet]

Branch: u/bruno/make__quo_rem__give_answers_more_often

[bgrenet]

Author: Bruno Grenet

[bgrenet]

Commit: 17ec8ea

[bgrenet]

New commits:

9000fb8	Add quo_rem method in class Polynomial_generic_sparse
84833c9	Move inversion of unit
fb1d21c	Add doc tests
17ec8ea	Try to compute the euclidean division, even for nonunit leading coefficients, until some non-exact division occurs

[fchapoton]

comment:5

needs rebase, does not apply