Opened 3 years ago
Closed 13 months ago
#21994 closed defect (fixed)
Change behavior of the % operator for padic integral elements
Reported by:  roed  Owned by:  

Priority:  major  Milestone:  sage7.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^(k1)
.
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 15 months ago by
comment:2 Changed 15 months ago by
I don't think I have any code for this.
comment:3 Changed 13 months ago by
 Keywords padicIMA added
comment:4 Changed 13 months ago by
 Branch set to u/roed/quo_rem_revision
comment:5 Changed 13 months ago by
 Commit set to fda8a55c3e1834e5d51db4e27d1ab28fc5ada18d
Branch pushed to git repo; I updated commit sha1. New commits:
fda8a55  Remove some lines that should be in 23218

comment:6 Changed 13 months ago by
 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 13 months ago by
 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 13 months ago by
 Branch changed from u/roed/quo_rem_revision to u/caruso/quo_rem_revision
comment:9 Changed 13 months ago by
 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:
634c8b8  Fix an issue with precision

450d11b  Add a generic implementation of quo_rem

9340a8a  Fix a corner case

comment:10 Changed 13 months ago by
 Status changed from needs_review to positive_review
comment:11 Changed 13 months ago by
 Branch changed from u/caruso/quo_rem_revision to u/roed/quo_rem_revision
comment:12 Changed 13 months ago by
 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 13 months ago by
 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 13 months ago by
 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 13 months ago by
I think that the variables powhelper_oneunit
, etc. aren't used in this ticket. (Probably they are in #23218.)
comment:16 Changed 13 months ago by
 Status changed from needs_review to positive_review
Patchbot is happy. I give a positive review to this ticket.
comment:17 Changed 13 months ago by
 Branch changed from u/roed/quo_rem_revision to 162b44d27c5099d830accc44d3f98ba73a099940
 Resolution set to fixed
 Status changed from positive_review to closed
Is there some code available somewhere?