Change behavior of the % operator for p-adic integral elements

[roed]

In padic_generic_element.pyx, the documentation for _mod_ describes two options for implementing a%b and a//b.

(2) If b = pi^k, the series expansion (in terms of pi) of a//b is just the series expansion of a, shifted over by k terms.

(2') The series expansion of a % pi^k has no terms above pi^(k-1).

The conditions (2) and (2') are equivalent. But when we generalize these conditions to arbitrary b they diverge.

(3) For general b, the series expansion of a//b is just the series expansion of a/b, truncating terms with negative exponents of pi.

(4) For general b, the series expansion of a%b has no terms above b.valuation() - 1.

In order to satisfy (3), one defines

a // b = (a / b.unit_part()) >> b.valuation()
a % b = a - (a // b) * b

In order to satisfy (4), one defines

a % b = a.lift() % pi.lift()^b.valuation()
a // b = ((a - a % b) >> b.valuation()) / b.unit_part()

Currently, Sage implements option (3). The justification given is that "it is more easily defined in terms of shifting and thus generalizes more easily to extension rings."

On the other hand, (4) behaves better in terms of precision: the remainder in the definition (4) is always known with the maximal precision (and actually to infinite precision) while in (3) we are loosing precision for the quotient and the remainder at the same time.

On a related note, when using definition (4), if u has valuation 0 then

a % (bu) = a % b
a // (bu) = (a // b) * u^(-1)

There is no corresponding simple relations if we are using definition (3).

In this ticket, we implement behavior (4) as an option and provide deprecation messages for behavior (3).

[caruso]

Is there some code available somewhere?

[roed]

I don't think I have any code for this.

[git]

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

​fda8a55

Remove some lines that should be in 23218

[roed]

All tests pass, but should still wait for remainder of patchbot report.

[git]

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

​2975633

Add _quo_rem to lattice precision

[caruso]

Looks good to me (after my update). Positive review if the patchbot is happy (but it probable won't...)

---

New commits:

​634c8b8	Fix an issue with precision
​450d11b	Add a generic implementation of quo_rem
​9340a8a	Fix a corner case

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​c0da7de

Update documentation

[git]

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

​c8ae6a7

Move the generic implementation of _quo_rem back from 23218

[git]

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

​634c8b8	Fix an issue with precision
​450d11b	Add a generic implementation of quo_rem
​9340a8a	Fix a corner case
​cabb63e	Merge branch 'u/caruso/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
​9662550	Merge branch 'u/roed/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
​162b44d	Fixing doctests, bad argument in floordiv

[caruso]

I think that the variables powhelper_oneunit, etc. aren't used in this ticket. (Probably they are in #23218.)

[caruso]

Patchbot is happy. I give a positive review to this ticket.