Opened 6 years ago

Closed 4 years ago

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

Reported by: Owned by: roed major sage-7.5 padics padicIMA caruso, saraedum David Roe Xavier Caruso N/A 162b44d 162b44d27c5099d830accc44d3f98ba73a099940

Description

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

comment:1 Changed 4 years ago by caruso

Is there some code available somewhere?

comment:2 Changed 4 years ago by roed

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

comment:4 Changed 4 years ago by roed

• Branch set to u/roed/quo_rem_revision

comment:5 Changed 4 years ago by git

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

 ​fda8a55 `Remove some lines that should be in 23218`

comment:6 Changed 4 years ago by roed

• Authors set to David Roe
• Reviewers set to Xavier Caruso
• Status changed from new to needs_review

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

comment:7 Changed 4 years ago by git

• Commit changed from fda8a55c3e1834e5d51db4e27d1ab28fc5ada18d to 297563333e40384847c8496b81b88171352b3713

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

 ​2975633 `Add _quo_rem to lattice precision`

comment:8 Changed 4 years ago by caruso

• Branch changed from u/roed/quo_rem_revision to u/caruso/quo_rem_revision

comment:9 Changed 4 years ago by caruso

• Commit changed from 297563333e40384847c8496b81b88171352b3713 to 9340a8a6e40b949ccefe1656451da35c98e81222

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

New commits:

 ​634c8b8 `Fix an issue with precision` ​450d11b `Add a generic implementation of quo_rem` ​9340a8a `Fix a corner case`
Last edited 4 years ago by caruso (previous) (diff)

comment:10 Changed 4 years ago by caruso

• Status changed from needs_review to positive_review

comment:11 Changed 4 years ago by roed

• Branch changed from u/caruso/quo_rem_revision to u/roed/quo_rem_revision

comment:12 Changed 4 years ago by git

• Commit changed from 9340a8a6e40b949ccefe1656451da35c98e81222 to c0da7de33e28d96b8cc5028661679dc213b40f18
• Status changed from positive_review to needs_review

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

 ​c0da7de `Update documentation`

comment:13 Changed 4 years ago by git

• Commit changed from c0da7de33e28d96b8cc5028661679dc213b40f18 to c8ae6a7b106498a67d8cdb1283ac1b78dd9d2ab5

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

 ​c8ae6a7 `Move the generic implementation of _quo_rem back from 23218`

comment:14 Changed 4 years ago by git

• Commit changed from c8ae6a7b106498a67d8cdb1283ac1b78dd9d2ab5 to 162b44d27c5099d830accc44d3f98ba73a099940

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`

comment:15 Changed 4 years ago by caruso

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

comment:16 Changed 4 years ago by caruso

• Status changed from needs_review to positive_review

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

comment:17 Changed 4 years ago by vbraun

• Branch changed from u/roed/quo_rem_revision to 162b44d27c5099d830accc44d3f98ba73a099940
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.