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: sage-7.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:

Status badges

Description (last modified by jdemeyer)

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__.

Change History (39)

comment:1 Changed 14 years ago by was

  • Type changed from defect to enhancement

comment:2 Changed 14 years ago by mabshoff

  • Milestone set to sage-2.9.1

comment:3 in reply to: ↑ description ; follow-up: Changed 14 years ago by 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 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().)

comment:4 in reply to: ↑ 3 Changed 13 years ago by jbmohler

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 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.

comment:5 Changed 13 years ago by jbmohler

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

comment:6 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 7 years ago by jdemeyer

  • 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 jdemeyer

  • Component changed from basic arithmetic to coercion
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-7.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 jdemeyer

  • Authors set to Jeroen Demeyer
  • Dependencies set to #2034

comment:13 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:14 Changed 5 years ago by jdemeyer

  • Cc vdelecroix added
  • Description modified (diff)

comment:15 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:16 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:17 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:18 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:19 follow-up: Changed 5 years ago by vdelecroix

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 jdemeyer

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 slow-down of these extra checks does not justify the few cases where the check might improve performance.

comment:21 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:22 Changed 5 years ago by jdemeyer

  • Branch set to u/jdemeyer/add___mod___to_coercion_model

comment:23 Changed 5 years ago by jdemeyer

  • Commit set to 82f22e0ccd1f16dd634b77a6afe3845406b52120
  • Status changed from new to needs_review

New commits:

5e8a5e3Implement __floordiv__ in the coercion model
835059fRemove redundant __floordiv__ from number field elements
3e0e5b8Add more doctests for floor division
82f22e0Implement __mod__ in the coercion model

comment:24 Changed 5 years ago by vdelecroix

  • Dependencies #2034 deleted
  • Status changed from needs_review to needs_work

Does not apply on last beta.

comment:25 Changed 5 years ago by git

  • Commit changed from 82f22e0ccd1f16dd634b77a6afe3845406b52120 to 665b8d127adb812a58e77b7d698c330030390d18

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

665b8d1Implement __mod__ in the coercion model

comment:26 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-7.1 to sage-7.3
  • Status changed from needs_work to needs_review

comment:27 Changed 5 years ago by vdelecroix

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 git

  • Commit changed from 665b8d127adb812a58e77b7d698c330030390d18 to b48a839723966365beae466e22d37e0564e9ad6a

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

b48a839Implement __mod__ in the coercion model

comment:29 Changed 5 years ago by git

  • Commit changed from b48a839723966365beae466e22d37e0564e9ad6a to 35b3dfa3a464f73426dd60a41bb681d15e2efcfb

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

35b3dfaImplement __mod__ in the coercion model

comment:30 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:31 Changed 5 years ago by git

  • Commit changed from 35b3dfa3a464f73426dd60a41bb681d15e2efcfb to 80795088d0774413d5cbb94459d95b430e9fe2ad

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

8079508Implement __mod__ in the coercion model

comment:32 Changed 5 years ago by vdelecroix

  • 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 git

  • Commit changed from 80795088d0774413d5cbb94459d95b430e9fe2ad to defac691ecb14f9b9832c7efcd1717c756f6ddd3

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

defac69Reimplement __mod__ for integer mods

comment:34 Changed 5 years ago by git

  • Commit changed from defac691ecb14f9b9832c7efcd1717c756f6ddd3 to 1d53754eaf18b3fb88267221ad4ba752c5cea2a1

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

1d53754Reimplement __mod__ for integer mods

comment:35 Changed 5 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:36 Changed 5 years ago by git

  • Commit changed from 1d53754eaf18b3fb88267221ad4ba752c5cea2a1 to aca3398a81b3688e1f2e69c5910b8214d13be925

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

aca3398Fix doctests for changed exception type

comment:37 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:38 Changed 5 years ago by jdemeyer

Thanks!

comment:39 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/add___mod___to_coercion_model to aca3398a81b3688e1f2e69c5910b8214d13be925
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.