Opened 3 years ago

Closed 16 months ago

#21994 closed defect (fixed)

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

Reported by: roed Owned by:
Priority: major Milestone: sage-7.5
Component: padics Keywords: padicIMA
Cc: caruso, saraedum Merged in:
Authors: David Roe Reviewers: Xavier Caruso
Report Upstream: N/A Work issues:
Branch: 162b44d (Commits) Commit: 162b44d27c5099d830accc44d3f98ba73a099940
Dependencies: Stopgaps:

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

Change History (17)

comment:1 Changed 19 months ago by caruso

Is there some code available somewhere?

comment:2 Changed 19 months ago by roed

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

comment:3 Changed 17 months ago by roed

  • Keywords padicIMA added

comment:4 Changed 17 months ago by roed

  • Branch set to u/roed/quo_rem_revision

comment:5 Changed 17 months ago by git

  • Commit set to fda8a55c3e1834e5d51db4e27d1ab28fc5ada18d

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

fda8a55Remove some lines that should be in 23218

comment:6 Changed 17 months 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 17 months ago by git

  • Commit changed from fda8a55c3e1834e5d51db4e27d1ab28fc5ada18d to 297563333e40384847c8496b81b88171352b3713

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

2975633Add _quo_rem to lattice precision

comment:8 Changed 17 months ago by caruso

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

comment:9 Changed 17 months 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 probable won't...)


New commits:

634c8b8Fix an issue with precision
450d11bAdd a generic implementation of quo_rem
9340a8aFix a corner case
Version 0, edited 17 months ago by caruso (next)

comment:10 Changed 17 months ago by caruso

  • Status changed from needs_review to positive_review

comment:11 Changed 17 months ago by roed

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

comment:12 Changed 17 months 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:

c0da7deUpdate documentation

comment:13 Changed 17 months ago by git

  • Commit changed from c0da7de33e28d96b8cc5028661679dc213b40f18 to c8ae6a7b106498a67d8cdb1283ac1b78dd9d2ab5

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

c8ae6a7Move the generic implementation of _quo_rem back from 23218

comment:14 Changed 17 months ago by git

  • Commit changed from c8ae6a7b106498a67d8cdb1283ac1b78dd9d2ab5 to 162b44d27c5099d830accc44d3f98ba73a099940

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

634c8b8Fix an issue with precision
450d11bAdd a generic implementation of quo_rem
9340a8aFix a corner case
cabb63eMerge branch 'u/caruso/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
9662550Merge branch 'u/roed/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
162b44dFixing doctests, bad argument in floordiv

comment:15 Changed 17 months 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 17 months 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 16 months 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.