make divides() better #25277

videlec · 2018-05-01T17:47:54Z

sage: R = Zmod(6)
sage: R(4).divides(R(2))
Traceback (most recent call last):
...
ArithmeticError: reduction modulo 4 not defined

See the relevant discussion on sage-devel.

Component: basic arithmetic

Author: Vincent Delecroix

Branch/Commit: 4a6cbd7

Reviewer: Travis Scrimshaw

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

The text was updated successfully, but these errors were encountered:

videlec · 2018-05-02T05:18:50Z

Commit: 2cf9010

videlec · 2018-05-02T05:18:50Z

Author: Vincent Delecroix

videlec · 2018-05-02T05:18:50Z

New commits:

`3fa3a95`	`25277: _test_divides in Rings()`
`2cf9010`	`25277: divides for integer mod ring`

videlec · 2018-05-02T05:18:50Z

Branch: u/vdelecroix/25277

tscrim · 2018-05-02T05:51:14Z

comment:3

IMO, it is better to do

-            S = tester.some_elements()
-            for a in S:
-                for b in S:
+            for a,b in tester.some_elements(repeat=2):

as then it runs max_runs number of times instead of max_runs².

sagetrac-git · 2018-05-02T08:37:07Z

Branch pushed to git repo; I updated commit sha1. New commits:

`cb2a1c3`	`25277: smarter iteration over pairs of elements`

sagetrac-git · 2018-05-02T08:37:07Z

Changed commit from 2cf9010 to cb2a1c3

videlec · 2018-05-02T08:37:22Z

comment:5

Replying to @tscrim:

IMO, it is better to do

good suggestion!

videlec · 2018-05-02T08:41:15Z

comment:6

though some rings are not ready for that yet...

sage -t --long src/sage/combinat/sf/macdonald.py  # 12 doctests failed
sage -t --long src/sage/combinat/ncsf_qsym/ncsf.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/sfa.py  # 1 doctest failed
sage -t --long src/sage/algebras/steenrod/steenrod_algebra.py  # 11 doctests failed
sage -t --long src/sage/structure/element.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/root_lattice_realization_algebras.py  # 1 doctest failed
sage -t --long src/sage/combinat/posets/moebius_algebra.py  # 7 doctests failed
sage -t --long src/sage/combinat/sf/k_dual.py  # 6 doctests failed
sage -t --long src/sage/combinat/ncsf_qsym/qsym.py  # 8 doctests failed
sage -t --long src/sage/combinat/sf/llt.py  # 10 doctests failed
sage -t --long src/sage/homology/homology_vector_space_with_basis.py  # 5 doctests failed
sage -t --long src/sage/combinat/grossman_larson_algebras.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/jack.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/classical.py  # 5 doctests failed
sage -t --long src/sage/combinat/sf/new_kschur.py  # 5 doctests failed
sage -t --long src/sage/modular/abvar/homspace.py  # 1 doctest failed
sage -t --long src/sage/algebras/yangian.py  # 4 doctests failed
sage -t --long src/sage/manifolds/chart_func.py  # 1 doctest failed
sage -t --long src/sage/algebras/quatalg/quaternion_algebra.py  # 2 doctests failed
sage -t --long src/sage/algebras/iwahori_hecke_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/sf.py  # 1 doctest failed
sage -t --long src/sage/algebras/cluster_algebra.py  # 6 doctests failed
sage -t --long src/sage/algebras/quantum_matrix_coordinate_algebra.py  # 3 doctests failed
sage -t --long src/sage/combinat/ncsym/ncsym.py  # 9 doctests failed
sage -t --long src/sage/combinat/sf/schur.py  # 2 doctests failed
sage -t --long src/sage/combinat/free_dendriform_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/symmetric_group_algebra.py  # 6 doctests failed
sage -t --long src/sage/combinat/sf/hall_littlewood.py  # 6 doctests failed
sage -t --long src/sage/categories/finite_dimensional_algebras_with_basis.py  # 2 doctests failed
sage -t --long src/sage/combinat/fqsym.py  # 3 doctests failed
sage -t --long src/sage/algebras/rational_cherednik_algebra.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/pbori.pyx  # 1 doctest failed
sage -t --long src/sage/manifolds/differentiable/scalarfield_algebra.py  # 3 doctests failed
sage -t --long src/sage/manifolds/scalarfield_algebra.py  # 3 doctests failed
sage -t --long src/sage/algebras/free_algebra.py  # 14 doctests failed
sage -t --long src/sage/algebras/lie_algebras/poincare_birkhoff_witt.py  # 2 doctests failed
sage -t --long src/sage/matrix/matrix_gap.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/diagram_algebras.py  # 5 doctests failed
sage -t --long src/sage/combinat/descent_algebra.py  # 4 doctests failed
sage -t --long src/sage/rings/real_mpfi.pyx  # 1 doctest failed
sage -t --long src/sage/structure/parent.pyx  # 1 doctest failed
sage -t --long src/sage/rings/real_mpfr.pyx  # 1 doctest failed
sage -t --long src/sage/algebras/commutative_dga.py  # 5 doctests failed
sage -t --long src/sage/algebras/nil_coxeter_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/posets/incidence_algebras.py  # 2 doctests failed
sage -t --long src/sage/rings/polynomial/polynomial_quotient_ring.py  # 1 doctest failed
sage -t --long src/sage/matrix/matrix_space.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/character.py  # 2 doctests failed
sage -t --long src/sage/combinat/root_system/weyl_characters.py  # 3 doctests failed
sage -t --long src/sage/algebras/hall_algebra.py  # 6 doctests failed
sage -t --long src/sage/rings/ring.pyx  # 1 doctest failed
sage -t --long src/sage/symbolic/ring.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/ncsym/dual.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/witt.py  # 2 doctests failed
sage -t --long src/sage/algebras/schur_algebra.py  # 1 doctest failed
sage -t --long src/sage/categories/modules_with_basis.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/orthotriang.py  # 2 doctests failed
sage -t --long src/sage/algebras/affine_nil_temperley_lieb.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/plural.pyx  # 2 doctests failed
sage -t --long src/sage/algebras/shuffle_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/dual.py  # 2 doctests failed
sage -t --long src/sage/categories/examples/with_realizations.py  # 4 doctests failed
sage -t --long src/sage/categories/magmas.py  # 1 doctest failed
sage -t --long src/sage/rings/power_series_ring_element.pyx  # 1 doctest failed
sage -t --long src/sage/algebras/yokonuma_hecke_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/monomial.py  # 2 doctests failed
sage -t --long src/sage/algebras/clifford_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/powersum.py  # 2 doctests failed
sage -t --long src/doc/en/thematic_tutorials/coercion_and_categories.rst  # 4 doctests failed
sage -t --long src/sage/combinat/sf/elementary.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/homogeneous.py  # 2 doctests failed
sage -t --long src/sage/categories/examples/graded_connected_hopf_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/rings/power_series_ring.py  # 9 doctests failed
sage -t --long src/sage/structure/category_object.pyx  # 2 doctests failed
sage -t --long src/doc/en/thematic_tutorials/tutorial-implementing-algebraic-structures.rst  # 1 doctest failed
sage -t --long src/sage/quivers/algebra.py  # 1 doctest failed
sage -t --long src/sage/rings/multi_power_series_ring.py  # 7 doctests failed
sage -t --long src/sage/rings/quotient_ring.py  # 1 doctest failed
sage -t --long src/sage/categories/hopf_algebras_with_basis.py  # 2 doctests failed
sage -t --long src/sage/algebras/tensor_algebra.py  # 2 doctests failed
sage -t --long src/sage/algebras/letterplace/free_algebra_letterplace.pyx  # 3 doctests failed
sage -t --long src/sage/rings/laurent_series_ring.py  # 7 doctests failed
sage -t --long src/sage/combinat/sf/symplectic.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/orthogonal.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/multiplicative.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/skew_polynomial_ring.py  # 2 doctests failed
sage -t --long src/sage/algebras/orlik_solomon.py  # 2 doctests failed
sage -t --long src/sage/algebras/weyl_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/series.py  # 1 doctest failed
sage -t --long src/sage/combinat/combinatorial_algebra.py  # 2 doctests failed
sage -t --long src/sage/categories/algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/hopf_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/algebras/free_algebra_quotient.py  # 1 doctest failed
sage -t --long src/sage/algebras/q_system.py  # 2 doctests failed
sage -t --long src/sage/symbolic/callable.py  # 1 doctest failed
sage -t --long src/sage/algebras/associated_graded.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/filtered_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/finite_dimensional_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/lie_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/algebras_with_basis.py  # 1 doctest failed

sagetrac-git · 2018-05-02T13:51:48Z

Changed commit from cb2a1c3 to f6ee03a

sagetrac-git · 2018-05-02T13:51:48Z

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

`431c27e`	`25277: _test_divides in Rings()`
`e09a5f3`	`25277: two better divides and one better _mod_`
`eb2ea8a`	`25277: doctests fix`
`f6ee03a`	`25277: skip _test_divides in the symbolic`

videlec · 2018-05-02T13:53:42Z

comment:8

This ticket fixes several problem with the divides method

First of all, a custom one is implemented on zmod rings

sage: R = Zmod(6)
sage: R(4).divides(R(2))
Traceback (most recent call last):
...
ArithmeticError: reduction modulo 4 not defined

(see the relevant discussion on sage-devel).

Secondly, make divides return NotImplementedError always when not available.

Finally, test this with a test method.

sagetrac-git · 2018-05-02T16:11:24Z

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

`7682bc2`	`25277: _test_divides in CommutativeRings()`
`722a965`	`25277: two better divides and one better _mod_`
`a03f964`	`25277: doctests fix`
`765598f`	`25277: skip _test_divides in the symbolic`

sagetrac-git · 2018-05-02T16:11:24Z

Changed commit from f6ee03a to 765598f

tscrim · 2018-05-02T21:16:59Z

comment:11

In comment:6, is "that" referring to comment:3 or this extra test?

videlec · 2018-05-02T21:31:54Z

comment:12

"that" meant "the extra _test_divides" included in this ticket.

videlec · 2018-05-02T21:32:47Z

comment:13

But I managed to find a solution with the latest commits.

tscrim · 2018-05-02T21:47:32Z

comment:14

Thank you. Yep, I see the difference. So the only thing that I am unsure of are these sorts of doctest changes:

             sage: subspace.change_ring(CC)
-            Subspace of dimension 2 of ModularForms(n=6, k=20, ep=1) over Complex Field with 53 bits of precision
+            Traceback (most recent call last):
+            ...
+            NotImplementedError

I would prefer someone who understands this code to see if they agree with these changes or not.

videlec · 2018-05-02T21:50:10Z

comment:15

Replying to @tscrim:

Thank you. Yep, I see the difference. So the only thing that I am unsure of are these sorts of doctest changes:
             sage: subspace.change_ring(CC)
-            Subspace of dimension 2 of ModularForms(n=6, k=20, ep=1) over Complex Field with 53 bits of precision
+            Traceback (most recent call last):
+            ...
+            NotImplementedError
I would prefer someone who understands this code to see if they agree with these changes or not.

There is nowhere a modular form with coefficients in CC that is constructed. And for a good reason: it would be completely broken (because it does use the % operator). These tests have been written only to test the change_ring method.

tscrim · 2018-05-02T21:59:47Z

comment:16

Replying to @videlec:

There is nowhere a modular form with coefficients in CC that is constructed. And for a good reason: it would be completely broken (because it does use the % operator). These tests have been written only to test the change_ring method.

Thank you for the explanation. If they are bogus tests, then why not remove them altogether? I also am not sure I like the inconsistency with QQ:

sage: CC(2,1).divides(CC(1,2))
True
sage: QQ(1/2).divides(QQ(2))
True
sage: 2 % (1/2)
...
TypeError: no conversion of this rational to integer

(this was tested on vanilla).

slel · 2018-05-02T22:06:27Z

comment:17

What is the relation with #25278?

videlec · 2018-05-02T22:12:39Z

comment:18

I am happy removing the tests. Will do it.

divides is not intended to be compatible with % but with *. Whether % means "remainder of the division" is not universally true as (1/2) % 3 shows. And for (exact) fields a.divides(b) should always return True unless a is zero. I don't think it is meaningful at all for non exact rings.

What kind of consistency would you require with %? The fact that it is the default implementation of divides is kind of error prone.

videlec · 2018-05-02T22:13:11Z

comment:19

Replying to @slel:

What is the relation with #25278?

your comment?

sagetrac-git · 2018-05-02T22:19:35Z

Branch pushed to git repo; I updated commit sha1. New commits:

`4a6cbd7`	`25277: remove useless tests`

sagetrac-git · 2018-05-02T22:19:35Z

Changed commit from 765598f to 4a6cbd7

tscrim · 2018-05-02T22:26:47Z

Reviewer: Travis Scrimshaw

tscrim · 2018-05-02T22:26:47Z

comment:21

Replying to @videlec:

I am happy removing the tests. Will do it.

Thank you.

divides is not intended to be compatible with % but with *. Whether % means "remainder of the division" is not universally true as (1/2) % 3 shows. And for (exact) fields a.divides(b) should always return True unless a is zero. I don't think it is meaningful at all for non exact rings.

What kind of consistency would you require with %? The fact that it is the default implementation of divides is kind of error prone.

I was mostly trying to compare CC and QQ to better understand why it only still works for the latter. I am not sure I actually do since you said it was because the % operator is used. However, such tests also fail for QQ generically; a % b only works if b is an integer, in which case it treats a as in Zmod(b). I'm going to set a positive review because it does not make the QQ test any less artificial than before this ticket, but it doesn't seem like a good test from my (uneducated) perspective.

videlec · 2018-05-03T06:59:18Z

comment:22

Thanks for the review!

About %: #21745 and #21747

vbraun · 2018-05-15T22:33:45Z

Changed branch from u/vdelecroix/25277 to 4a6cbd7

videlec added this to the sage-8.3 milestone May 1, 2018

videlec added c: basic arithmetic labels May 1, 2018

jdemeyer changed the title ~~divides should never fail~~ divides() fails in IntegerModRing May 1, 2018

videlec added the s: needs review label May 2, 2018

videlec added s: needs work and removed s: needs review labels May 2, 2018

videlec added s: needs review and removed s: needs work labels May 2, 2018

videlec changed the title ~~divides() fails in IntegerModRing~~ make divides() better May 2, 2018

tscrim added s: positive review and removed s: needs review labels May 2, 2018

vbraun removed the s: positive review label May 15, 2018

vbraun closed this as completed in eac954c May 15, 2018

bgrenet mentioned this issue Aug 26, 2018

Add a method divides to Polynomial #19171

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

make divides() better #25277

make divides() better #25277

videlec commented May 1, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

slel commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

tscrim commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 3, 2018

vbraun commented May 15, 2018

make divides() better #25277

make divides() better #25277

Comments

videlec commented May 1, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 2, 2018

tscrim commented May 2, 2018

slel commented May 2, 2018

videlec commented May 2, 2018

videlec commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

sagetrac-git mannequin commented May 2, 2018

tscrim commented May 2, 2018

tscrim commented May 2, 2018

videlec commented May 3, 2018

vbraun commented May 15, 2018