Add __mod__ to coercion model

[sagetrac-dmharvey]

Add __mod__ to the coercion model for Element and change __mod__ to _mod_ where applicable.

We change the behaviour of __mod__ for integer mod rings: the following (which is mathematically meaningless) is now an error:

             sage: a = next_prime(2**31)
             sage: b = Integers(a)(100)
             sage: a % b
             Traceback (most recent call last):
             ...
             ZeroDivisionError: reduction modulo 100 not defined

Apart from this, this branch does not change any semantics of remaindering.

As proof-of-concept for refactoring more generally the arithmetic methods on Element, the implementation of __mod__ is different from the usual implementation:

1. _mod_ will be added to Element and not RingElement or similar.
2. The prototype is cpdef _mod_(self, other) with no typing for the arguments or return value.
3. We do not implement the in-place __imod__ which is useless anyway with coercion.

My intention is that eventually all arithmetic methods should be implemented like __mod__.

CC: @videlec

Component: coercion

Author: Jeroen Demeyer

Branch/Commit: aca3398

Reviewer: Vincent Delecroix

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

[sagetrac-cwitty]

Replying to @sagetrac-dmharvey:

So far we only have add, sub, neg, various versions of mul, and div.

We also need floordiv, mod, invert, pow.

These would be very useful in p-adics, and need to happen for other reasons too.

Is exact division (that is, division where the caller knows that there is no remainder) common enough to belong here? (There's an implementation for Integer already, where the method is called divide_knowing_divisible_by() and calls mpz_divexact().)

[sagetrac-jbmohler]

comment:4

Replying to @sagetrac-cwitty:

Replying to @sagetrac-dmharvey:

So far we only have add, sub, neg, various versions of mul, and div.

We also need floordiv, mod, invert, pow.

These would be very useful in p-adics, and need to happen for other reasons too.

Is exact division (that is, division where the caller knows that there is no remainder) common enough to belong here? (There's an implementation for Integer already, where the method is called divide_knowing_divisible_by() and calls mpz_divexact().)

I definitely think that exact division should be included in the arithmetic architecture. This is not because it's common, but because there is a bunch of daft coercion code in most !floordiv! implementations. All this needs to be fixed and the fix is a common boiler-plate prefix on these functions. Or, a much better alternative is to include it in the arithmetic hierarchy and write that boilerplate coercion once at the head of the tree.

I think that gcd (and maybe xgcd) should also be on this list.

[sagetrac-jbmohler]

comment:5

Oh, and quo_rem should be here too -- #383

[jdemeyer]

Dependencies: #2034

[jdemeyer]

Author: Jeroen Demeyer

[videlec]

comment:27

About comment:19 I guess that the rationale is that we should follow what was done until now. If you want to change the cpdef methods without declaring them as Element or ModuleElement or whatever I guess you should open a new ticket.

[sagetrac-git]

Changed commit from 665b8d1 to b48a839

[sagetrac-git]

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

b48a839

Implement `__mod__` in the coercion model

[sagetrac-git]

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

35b3dfa

Implement `__mod__` in the coercion model

[sagetrac-git]

Changed commit from b48a839 to 35b3dfa

[sagetrac-git]

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

8079508

Implement `__mod__` in the coercion model

[sagetrac-git]

Changed commit from 35b3dfa to 8079508

[videlec]

comment:32

Please, add doctests for __mod__ in sage.rings.finite_rings.integer_mod.

[videlec]

Reviewer: Vincent Delecroix

[sagetrac-git]

Changed commit from 8079508 to defac69

[sagetrac-git]

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

defac69

Reimplement `__mod__` for integer mods

[sagetrac-git]

Changed commit from defac69 to 1d53754

[sagetrac-git]

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

1d53754

Reimplement `__mod__` for integer mods

[sagetrac-git]

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

aca3398

Fix doctests for changed exception type

[sagetrac-git]

Changed commit from 1d53754 to aca3398

[jdemeyer]

comment:38

Thanks!

[vbraun]

Changed branch from u/jdemeyer/add___mod___to_coercion_model to aca3398