Opened 14 years ago
Closed 5 years ago
#269 closed enhancement (fixed)
Add __mod__ to coercion model
Reported by:  dmharvey  Owned by:  somebody 

Priority:  major  Milestone:  sage7.3 
Component:  coercion  Keywords:  
Cc:  vdelecroix  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  aca3398 (Commits, GitHub, GitLab)  Commit:  aca3398a81b3688e1f2e69c5910b8214d13be925 
Dependencies:  Stopgaps: 
Description (last modified by )
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 proofofconcept for refactoring more generally the arithmetic methods on Element
, the implementation of __mod__
is different from the usual implementation:
_mod_
will be added toElement
and notRingElement
or similar. The prototype is
cpdef _mod_(self, other)
with no typing for the arguments or return value.  We do not implement the inplace
__imod__
which is useless anyway with coercion.
My intention is that eventually all arithmetic methods should be implemented like __mod__
.
Change History (39)
comment:1 Changed 14 years ago by
 Type changed from defect to enhancement
comment:2 Changed 14 years ago by
 Milestone set to sage2.9.1
comment:3 in reply to: ↑ description ; followup: ↓ 4 Changed 14 years ago by
comment:4 in reply to: ↑ 3 Changed 13 years ago by
Replying to cwitty:
Replying to 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 padics, 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 boilerplate 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.
comment:5 Changed 13 years ago by
Oh, and quo_rem should be here too  #383
comment:6 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:7 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:8 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:9 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:10 Changed 7 years ago by
 Description modified (diff)
 Report Upstream set to N/A
 Summary changed from add floordiv, mod, invert, pow to arithmetic architecture (at least in RingElement) to Add floordiv and mod to arithmetic architecture (at least in RingElement)
comment:11 Changed 5 years ago by
 Component changed from basic arithmetic to coercion
 Description modified (diff)
 Milestone changed from sage6.4 to sage7.1
 Summary changed from Add floordiv and mod to arithmetic architecture (at least in RingElement) to Add __mod__ to coercion model
comment:12 Changed 5 years ago by
 Dependencies set to #2034
comment:13 Changed 5 years ago by
 Description modified (diff)
comment:14 Changed 5 years ago by
 Cc vdelecroix added
 Description modified (diff)
comment:15 Changed 5 years ago by
 Description modified (diff)
comment:16 Changed 5 years ago by
 Description modified (diff)
comment:17 Changed 5 years ago by
 Description modified (diff)
comment:18 Changed 5 years ago by
 Description modified (diff)
comment:19 followup: ↓ 20 Changed 5 years ago by
Jeroen, what is the rationale for
cpdef _mod_(self, Element other)
instead of
cpdef Element _mod_(self, Element other)
In a situtation like e1._mod_(e2)._add_(e3)
Cython would be happier. No?
comment:20 in reply to: ↑ 19 Changed 5 years ago by
Replying to vdelecroix:
In a situtation like
e1._mod_(e2)._add_(e3)
Cython would be happier. No?
Sure, but I don't know how common that is.
I want to avoid unneeded checking. If you do something like
cpdef Element _foo_(self, other): x = ... return x
then Cython will add a check that x
is actually of type Element
. I think (but this is just a wild guess) that the slowdown of these extra checks does not justify the few cases where the check might improve performance.
comment:21 Changed 5 years ago by
 Description modified (diff)
comment:22 Changed 5 years ago by
 Branch set to u/jdemeyer/add___mod___to_coercion_model
comment:23 Changed 5 years ago by
 Commit set to 82f22e0ccd1f16dd634b77a6afe3845406b52120
 Status changed from new to needs_review
comment:24 Changed 5 years ago by
 Dependencies #2034 deleted
 Status changed from needs_review to needs_work
Does not apply on last beta.
comment:25 Changed 5 years ago by
 Commit changed from 82f22e0ccd1f16dd634b77a6afe3845406b52120 to 665b8d127adb812a58e77b7d698c330030390d18
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
665b8d1  Implement __mod__ in the coercion model

comment:26 Changed 5 years ago by
 Milestone changed from sage7.1 to sage7.3
 Status changed from needs_work to needs_review
comment:27 Changed 5 years ago by
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.
comment:28 Changed 5 years ago by
 Commit changed from 665b8d127adb812a58e77b7d698c330030390d18 to b48a839723966365beae466e22d37e0564e9ad6a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b48a839  Implement __mod__ in the coercion model

comment:29 Changed 5 years ago by
 Commit changed from b48a839723966365beae466e22d37e0564e9ad6a to 35b3dfa3a464f73426dd60a41bb681d15e2efcfb
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
35b3dfa  Implement __mod__ in the coercion model

comment:30 Changed 5 years ago by
 Description modified (diff)
comment:31 Changed 5 years ago by
 Commit changed from 35b3dfa3a464f73426dd60a41bb681d15e2efcfb to 80795088d0774413d5cbb94459d95b430e9fe2ad
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8079508  Implement __mod__ in the coercion model

comment:32 Changed 5 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
Please, add doctests for __mod__
in sage.rings.finite_rings.integer_mod
.
comment:33 Changed 5 years ago by
 Commit changed from 80795088d0774413d5cbb94459d95b430e9fe2ad to defac691ecb14f9b9832c7efcd1717c756f6ddd3
Branch pushed to git repo; I updated commit sha1. New commits:
defac69  Reimplement __mod__ for integer mods

comment:34 Changed 5 years ago by
 Commit changed from defac691ecb14f9b9832c7efcd1717c756f6ddd3 to 1d53754eaf18b3fb88267221ad4ba752c5cea2a1
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
1d53754  Reimplement __mod__ for integer mods

comment:35 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:36 Changed 5 years ago by
 Commit changed from 1d53754eaf18b3fb88267221ad4ba752c5cea2a1 to aca3398a81b3688e1f2e69c5910b8214d13be925
Branch pushed to git repo; I updated commit sha1. New commits:
aca3398  Fix doctests for changed exception type

comment:37 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:38 Changed 5 years ago by
Thanks!
comment:39 Changed 5 years ago by
 Branch changed from u/jdemeyer/add___mod___to_coercion_model to aca3398a81b3688e1f2e69c5910b8214d13be925
 Resolution set to fixed
 Status changed from positive_review to closed
Replying to dmharvey:
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().)