Opened 8 years ago

Closed 6 years ago

Last modified 6 years ago

#12555 closed enhancement (fixed)

Reimplement elements of Zp and Qp using templates

Reported by: roed Owned by: roed
Priority: major Milestone: sage-6.1
Component: padics Keywords: sd53 padics templates
Cc: sydahmad, justin, wstein, JStarx, jpflori Merged in:
Authors: David Roe, Julian Rueth Reviewers: William Stein, Soroosh Yazdani, Julian Rueth, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: public/padics/templates-12555 (Commits) Commit: aa65f59d6fefe38a06f7577b0d98906242882fd0
Dependencies: #12625, #13299, #14287, #12575, #6223 Stopgaps:

Description (last modified by saraedum)

The goal of this ticket is to reimplement elements of Zp and Qp using the ideas from sage/rings/polynomial/polynomial_template.pxi. This should make p-adics in Sage both easier to maintain and easier to add new classes.

The final patch should not affect the external interface to Zp and Qp.


Apply

Attachments (17)

12555.patch (105.7 KB) - added by roed 8 years ago.
Still some bugs, but it should be useable to compare timings
12555_2.patch (404.3 KB) - added by roed 8 years ago.
I've fixed all known bugs; currently doctesting
12555_printing.patch (5.6 KB) - added by roed 8 years ago.
12555_remove_base_coerce.patch (30.9 KB) - added by roed 8 years ago.
12555_conv.patch (14.4 KB) - added by roed 8 years ago.
12555_remove_base.patch (32.9 KB) - added by roed 8 years ago.
12555_linkage.patch (42.6 KB) - added by roed 8 years ago.
12555_template.patch (15.5 KB) - added by roed 8 years ago.
12555_FM.patch (76.8 KB) - added by roed 8 years ago.
12555_CR.patch (159.3 KB) - added by roed 8 years ago.
12555_CA.patch (88.6 KB) - added by roed 8 years ago.
trac_12555-referee.patch (63.3 KB) - added by was 8 years ago.
this is my REFEREE patch after reading through half the code. I stopped at padic_ZZ_pX_FM_element.pyx. This is the ultimate patch bomb. Very hard to referee…
trac_12555_review.patch (816 bytes) - added by saraedum 7 years ago.
review patch to match changes done in 5.9.beta0
trac_12555.patch (547.4 KB) - added by roed 6 years ago.
combined github patch
12555_rebase_6223.patch (2.2 KB) - added by roed 6 years ago.
trac_12555_doc_improvements.patch (7.2 KB) - added by roed 6 years ago.
trac_12555-pdf_fix-ts.patch (4.9 KB) - added by tscrim 6 years ago.

Download all attachments as: .zip

Change History (105)

comment:1 in reply to: ↑ description Changed 8 years ago by sydahmad

  • Cc sydahmad added

Replying to roed:

The goal of this ticket is to reimplement elements of Zp and Qp using the ideas from sage/rings/polynomial/polynomial_template.pxi. This should make p-adics in Sage both easier to maintain and easier to add new classes.

comment:2 Changed 8 years ago by roed

  • Cc justin added

comment:3 Changed 8 years ago by roed

  • Description modified (diff)

Now includes capped absolute and fixed modulus elements. There are a few problems remaining:

  • teichmuller_list is disabled since it had a bug and I didn't want to fix it at the time. I'll track this down later.
  • Some coercions aren't working since the element class has changed.

This version should be enough for Justin to compare the performance of the templated and non-templated versions. I'm now going to create another patch on top of this which removes the untemplated versions.

Changed 8 years ago by roed

Still some bugs, but it should be useable to compare timings

Changed 8 years ago by roed

I've fixed all known bugs; currently doctesting

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

Changed 8 years ago by roed

comment:4 Changed 8 years ago by roed

  • Authors set to David Roe
  • Cc wstein JStarx added
  • Status changed from new to needs_review

comment:5 Changed 8 years ago by roed

  • Dependencies set to #12625, #12575

Changed 8 years ago by was

this is my REFEREE patch after reading through half the code. I stopped at padic_ZZ_pX_FM_element.pyx. This is the ultimate patch bomb. Very hard to referee...

comment:6 Changed 7 years ago by saraedum

  • Reviewers set to William Stein, Soroosh Yazdani, Julian Rueth
  • Status changed from needs_review to needs_work

A review of this patch is at https://github.com/saraedum/padic-review/commit. We agreed to work on the remaining issues there.

comment:7 Changed 7 years ago by roed

  • Dependencies changed from #12625, #12575 to #12625, #12575, #14106

comment:8 follow-up: Changed 7 years ago by roed

  • Milestone changed from sage-5.8 to sage-5.7

I've made a pull request to https://github.com/saraedum/padic-review/commit, addressing the comments. Tests all pass for me.

We had discussed having a document that runs some overall tests. I haven't made that yet, but can this week. If someone has time to take a look at this this week, I'll be available to make changes....

comment:9 in reply to: ↑ 8 ; follow-up: Changed 7 years ago by saraedum

Replying to roed:

I've made a pull request to https://github.com/saraedum/padic-review/commit, addressing the comments. Tests all pass for me.

Great.

We had discussed having a document that runs some overall tests. I haven't made that yet, but can this week. If someone has time to take a look at this this week, I'll be available to make changes....

You haven't started to work on this already, have you? I just started to work on these tests. I'll push to github as soon as I have something working.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 7 years ago by roed

We had discussed having a document that runs some overall tests. I haven't made that yet, but can this week. If someone has time to take a look at this this week, I'll be available to make changes....

You haven't started to work on this already, have you? I just started to work on these tests. I'll push to github as soon as I have something working.

No, I haven't started. I'll wait to see what you come up with.

Do we have a list of things that need to be done before this gets a positive review?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by saraedum

Replying to roed:

Do we have a list of things that need to be done before this gets a positive review?

Not yet. Should we use github issues for this?

comment:12 in reply to: ↑ 11 Changed 7 years ago by roed

Replying to saraedum:

Replying to roed:

Do we have a list of things that need to be done before this gets a positive review?

Not yet. Should we use github issues for this?

Sure, that sounds good.

comment:13 Changed 7 years ago by saraedum

  • Dependencies changed from #12625, #12575, #14106 to #12625, #12575, #14106, #14285

comment:14 Changed 7 years ago by saraedum

apply trac_12555.patch

comment:15 Changed 7 years ago by saraedum

  • Description modified (diff)

comment:16 Changed 7 years ago by saraedum

  • Dependencies changed from #12625, #12575, #14106, #14285 to #12625, #12575, #14106, #14284

comment:17 Changed 7 years ago by saraedum

  • Dependencies changed from #12625, #12575, #14106, #14284 to #12625, #12575, #14106, #14284, #14287

comment:18 Changed 7 years ago by roed

  • Dependencies changed from #12625, #12575, #14106, #14284, #14287 to #12625, #12575, #13299, #14284, #14287

comment:19 Changed 7 years ago by roed

  • Dependencies changed from #12625, #12575, #13299, #14284, #14287 to #12625, #12575, #13299, #14287

comment:20 Changed 7 years ago by saraedum

apply trac_12555.patch

comment:21 Changed 7 years ago by saraedum

  • Dependencies changed from #12625, #12575, #13299, #14287 to #12625, #13299, #14287, #12575

comment:22 Changed 7 years ago by saraedum

  • Status changed from needs_work to needs_review

comment:23 Changed 7 years ago by saraedum

apply trac_12555.patch

comment:24 Changed 7 years ago by saraedum

apply trac_12555.patch

comment:25 Changed 7 years ago by saraedum

  • Authors changed from David Roe to David Roe, Julian Rueth
  • Status changed from needs_review to positive_review

comment:26 Changed 7 years ago by saraedum

apply trac_12555.patch

Changed 7 years ago by saraedum

review patch to match changes done in 5.9.beta0

comment:27 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.7 to sage-5.9

comment:28 Changed 6 years ago by roed

  • Description modified (diff)
  • Milestone changed from sage-5.9 to sage-5.7

comment:29 Changed 6 years ago by roed

  • Milestone changed from sage-5.7 to sage-5.9

comment:30 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.9 to sage-pending

comment:31 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.10

comment:32 Changed 6 years ago by jdemeyer

  • Dependencies changed from #12625, #13299, #14287, #12575 to #12625, #13299, #14287, #12575, #6223
  • Status changed from positive_review to needs_work

Please rebase to #6223.

comment:33 Changed 6 years ago by jdemeyer

  • Status changed from needs_work to positive_review

comment:34 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This still needs work rebasing to #6223. Also PyErr_Occured() should not be used anymore in favour of standard Python except handling.

comment:35 Changed 6 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:36 Changed 6 years ago by jdemeyer

comment:37 Changed 6 years ago by jpflori

  • Cc jpflori added

comment:38 Changed 6 years ago by roed

  • Status changed from needs_review to positive_review

Those changes look fine to me.

comment:39 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Please fix this documentation problem (I won't):

[139 [690]] [130
! Missing $ inserted.
<inserted text> 
                $
l.10592 $i^{\mbox{prec_cap}
                           }$ if the element was defined by
? ]
! Emergency stop.
<inserted text> 
                $
l.10592 $i^{\mbox{prec_cap}
                           }$ if the element was defined by
!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on padics.log.
 [17make[1]: *** [padics.pdf] Error 1
make[1]: Leaving directory `/mazur/release/merger/sage-5.10.beta1/devel/sage-main/doc/output/latex/en/reference/padics'

comment:40 Changed 6 years ago by jdemeyer

* ping *

comment:41 Changed 6 years ago by roed

Thanks for the ping. I had a visitor this week, but he just left so I'll take a look.

Changed 6 years ago by roed

combined github patch

Changed 6 years ago by roed

Changed 6 years ago by roed

comment:42 Changed 6 years ago by roed

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Sorry for the long delay: I've been mostly working on research rather than Sage this summer.

I was unable to reproduce the documentation problem that you observed by running sage -docbuild reference html. Is there something I should do instead, or somewhere with a more complete log of the problem? I'm not quite sure what needs to be fixed.

I did go through and change most of the dollar signs in the p-adics directory to backticks, and updated these patches against Sage 5.10.

comment:43 follow-up: Changed 6 years ago by tscrim

I think Jeroen was refering to the pdf doc:

sage -docbuild all pdf

maybe?

For patchbot:

Apply: trac_12555.patch trac_12555_review.patch 12555_rebase_6223.patch trac_12555_doc_improvements.patch

comment:44 in reply to: ↑ 43 Changed 6 years ago by roed

Replying to tscrim:

I think Jeroen was refering to the pdf doc:

sage -docbuild all pdf

maybe?

Cool. I will try that overnight.

comment:45 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by tscrim

comment:46 Changed 6 years ago by tscrim

  • Description modified (diff)

Okay, I fixed the pdf docbuild issue and made some minor tweaks to that file.

Build finished.  The built documents can be found in /home/travis/sage-5.11.rc0/devel/sage/doc/output/pdf/en/reference/padics

If you're happy with my tweaks, we can set this (back to) positive review.

For patchbot:

Apply: trac_12555.patch, trac_12555_review.patch, 12555_rebase_6223.patch, trac_12555_doc_improvements.patch, trac_12555-pdf_fix-ts.patch​

Last edited 6 years ago by tscrim (previous) (diff)

comment:47 Changed 6 years ago by roed

Thanks! I've been trying to focus on writing papers this summer rather than Sage. I'm happy with the changes.

comment:48 Changed 6 years ago by tscrim

  • Reviewers changed from William Stein, Soroosh Yazdani, Julian Rueth to William Stein, Soroosh Yazdani, Julian Rueth, Travis Scrimshaw
  • Status changed from needs_review to positive_review

I'm interpreting that as a positive review.

comment:49 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Needs to be rebased to sage-5.12.beta3.

comment:50 Changed 6 years ago by saraedum

  • Branch set to u/saraedum/ticket/12555
  • Modified changed from 08/25/13 09:32:42 to 08/25/13 09:32:42

comment:51 Changed 6 years ago by saraedum

  • Description modified (diff)
  • Milestone changed from sage-5.12 to sage-6.0
  • Status changed from needs_work to positive_review

comment:52 Changed 6 years ago by jpflori

It seems to me this does not apply cleanly anymore to what I got when I clone Sage's git branch "build_system" as of today. I've pushed a hopefully correctly rebased branch to:

  • u/jpflori/12555

Best, JP

comment:53 Changed 6 years ago by jpflori

  • Keywords sd53 padics templates added

comment:54 Changed 6 years ago by jpflori

  • Branch changed from u/saraedum/ticket/12555 to u/jpflori/12555

comment:55 Changed 6 years ago by jpflori

  • Branch changed from u/jpflori/12555 to u/jpflori/ticket/12555

comment:56 Changed 6 years ago by ohanar

  • Commit set to 4b633ab664fd5bd062d29fcec78972232cde634c

New commits:

4b633abFixes for some missing/duplicated chunks.
66e5746From Trac patches: trac_12555-pdf_fix-ts.patch.
4e209b8From Trac patches: trac_12555_doc_improvements.patch​.
69d30a4From Trac patches: 12555_rebase_6223.patch.
11ad661From Trac patches: trac_12555_review.patch.
bd94fe3From Trac patches: trac_12555.patch.
a1f9becMerge remote-tracking branch 'origin/build_system' into build_system
4cb7db9Merge remote-tracking branch 'origin' into build_system

comment:57 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:58 Changed 6 years ago by vbraun

Conflicts with current release - git merge master & resolve

comment:59 Changed 6 years ago by tscrim

  • Branch changed from u/jpflori/ticket/12555 to public/padics/templates-12555
  • Commit changed from 4b633ab664fd5bd062d29fcec78972232cde634c to 7d7ff1fe557a360b590f8072f6da1abb9460b39e

I've uploaded a branch with the merge. I'm recompiling now and will test it shortly.


New commits:

7d7ff1fMerge branch 'master' into public/padics/templates-12555

comment:60 Changed 6 years ago by git

  • Commit changed from 7d7ff1fe557a360b590f8072f6da1abb9460b39e to 0e7c96482eb0d2ee036906c79ecbc122f3650eda
  • 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:

0e7c964Fixed failing doctest (likely due to #15422).

comment:61 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:62 Changed 6 years ago by vbraun

Conflicts with sage-6.1.beta1, please fix

comment:63 Changed 6 years ago by tscrim

I'm not familiar enough with the code to do this merge. David, Julian, could one of you do the merge?

comment:64 follow-up: Changed 6 years ago by jpflori

The problem is with commit fcf7972 "adapt miscellaneous files in the Sage library" which deals with Pari stuff. Note sure from which trac ticket this is: <hint hint> put trac ticket number into git commit messages... I'll fix it later today (currently my touchpad does not click, I cannot reboot, and tabbing all over the place is not so nice).

comment:65 in reply to: ↑ 64 Changed 6 years ago by jdemeyer

Replying to jpflori:

Note sure from which trac ticket this is

#15185

<hint hint> put trac ticket number into git commit messages...

If you have to ask people, that's not going to work. When I started as release manager, I asked that and people forgot, were lazy, put the wrong number... or worse: got angry because I was complaining over such trivial things like ticket numbers in commit messages.

I learned that the only feasible solution is to have a system which automatically added the ticket number to the commit message. With git that cannot be done (that would be rewriting history), but at least automating the mapping commit -> ticket number could be done some other way.

comment:66 Changed 6 years ago by vbraun

Don't put trac ticket numbers in the commit message, its useless double book-keeping. Its trivial to extract from the commit tree, e.g. using my "git trac" subcommand scripts it:

$ git trac find fcf7972
Commit has been merged by the release manager into your current branch.
commit c04a8de608cd41ed9d7ffbe250656bce03683301
Merge: 69b08fa 7ec74e0
Author: Release Manager <release@sagemath.org>
Date:   Fri Dec 20 13:21:14 2013 +0000

    Trac #15185: Clean up interface to the PARI library
    
    The file `sage/libs/pari/gen.pyx` is too big and contains too many
    different things.  For clarity and maintainability, it should be split
    into two parts:
    - `gen.pyx` containing the class `gen`;
    - `pari_instance.pyx` containing the class `PariInstance` and some
    utility functions;
    More cleaning-up will be done in #15461.
    
    URL: http://trac.sagemath.org/15185
    Reported by: pbruin
    Ticket author(s): Peter Bruin
    Reviewer(s): Jeroen Demeyer

comment:67 Changed 6 years ago by jdemeyer

jdemeyer@tamiyo:/usr/local/src/sage-git$ git trac find fcf7972
git: 'trac' is not a git command. See 'git --help'.

Did you mean this?
        branch

comment:68 Changed 6 years ago by jdemeyer

Rebasing to #15185 should be easy, it doesn't make any fundamental changes, only moves stuff around...

comment:70 Changed 6 years ago by jdemeyer

vbraun: Are there any plans to make that script part of Sage?

comment:71 Changed 6 years ago by vbraun

I think they are now ready to be used by a wider audience. Will make a package...

comment:72 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:73 Changed 6 years ago by git

  • Commit changed from 0e7c96482eb0d2ee036906c79ecbc122f3650eda to 5f0081329eb8dd9f843cf66c9f73a99d045ff53a

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

5f00813Fixes for "sage not defined".
89ef12dMerge remote-tracking branch 'origin/develop' into ticket/12555

comment:74 Changed 6 years ago by jpflori

Still some errors in src/sage/schemes/elliptic_curves/constructor.py and ell_egros.py raising:

SystemError: error return without exception set

when computing padic elliptic logs. Not sure where this comes from, maybe related to #15299.

comment:75 Changed 6 years ago by jpflori

Apparently its when testing

y1 == -y2 - a1*x2 - a3

in ell_point.py. The following reproduces it:

sage: y1 = 10*11^2 + 3*11^3 + O(11^40)
sage: y2 = 11^2 + 7*11^3 + 10*11^4 + 10*11^5 + 10*11^6 + 10*11^7 + 10*11^8 + 10*11^9 + 10*11^10 + 10*11^11 + 10*11^12 + 10*11^13 + 10*11^14 + 10*11^15 + 10*11^16 + 10*11^17 + 10*11^18 + 10*11^19 + 10*11^20 + 10*11^21 + 10*11^22 + 10*11^23 + 10*11^24 + 10*11^25 + 10*11^26 + 10*11^27 + 10*11^28 + 10*11^29 + 10*11^30 + 10*11^31 + 10*11^32 + 10*11^33 + 10*11^34 + 10*11^35 + 10*11^36 + 10*11^37 + 10*11^38 + 10*11^39 + O(11^40)
sage: y1 == y2
---------------------------------------------------------------------------
SystemError                               Traceback (most recent call last)
<ipython-input-4-2a7abc374794> in <module>()
----> 1 y1 == y2

SystemError: error return without exception set
sage: 

comment:76 Changed 6 years ago by jpflori

Ok it seems its just that mpz_cmp decides to return -2 which is also set as the except value.

comment:77 Changed 6 years ago by git

  • Commit changed from 5f0081329eb8dd9f843cf66c9f73a99d045ff53a to fcf6ad2787c40314bd51953d21967af4a6c70297

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

fcf6ad2Fix for comparison of padics.

comment:78 Changed 6 years ago by jpflori

  • Status changed from needs_work to needs_review

Should be ok now. May be worth putting an additional test in there, but I'm too tired now and the code is already tested by the previous bug.

comment:79 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

That example (and testing the files) now works for me, so it's back to positive review.

EDIT - also I don't think .pxi files are run as part of doctesting?

Last edited 6 years ago by tscrim (previous) (diff)

comment:80 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:81 Changed 6 years ago by vbraun

  • Resolution fixed deleted
  • Status changed from closed to new

Documentation doesn't build

[padics   ] /mnt/SSD1/mod_buildslave/sage_git/build/src/doc/en/reference/padics/sage/rings/padics/padic_base_generic_element.rst:11: WARNING: autodoc can't import/find module 'sage.rings.padics.padic_base_generic_element', it reported error: "No module named padic_base_generic_element", please check your spelling and sys.path
[padics   ] docstring of sage.rings.padics.padic_fixed_mod_element:9: ERROR: Unknown directive type "NOTES".

comment:82 Changed 6 years ago by git

  • Commit changed from fcf6ad2787c40314bd51953d21967af4a6c70297 to f338b7fa5d11807a7c8dcde2ce745858e6cf047c

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

f338b7fFix wrong NOTE block.

comment:83 Changed 6 years ago by git

  • Commit changed from f338b7fa5d11807a7c8dcde2ce745858e6cf047c to aa65f59d6fefe38a06f7577b0d98906242882fd0

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

aa65f59Removed removed file from doc.

comment:84 Changed 6 years ago by tscrim

  • Status changed from new to needs_review

New commits:

aa65f59Removed removed file from doc.

comment:85 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:86 Changed 6 years ago by niles

There are a number of other power series bugs that have been waiting in one way or another for rewriting of padics. Could someone here take a look and comment on the appropriate tickets? They do not seem to be resolved by this one.

#9457: Buggy equality of power series -- The fix seems straightforward, but causes a bizarre doctest failure in sha_tate.py

#4656: Power series over p-adics treat inexact zeros inconsistently -- The fix here causes the same doctest to fail.

#8198: p-adic precision is dropped when matrix acts on vector -- Possibly a root cause of the previous two bugs.

#5075: Polynomials over inexact rings truncate inexact leading zeroes -- This was somehow fixed for polynomials over p-adics, but polynomials over other power series still have the issue. David Roe commented that it may be fixed as part of a larger patch (I hope there's not another one after this!)

comment:87 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:88 Changed 6 years ago by jdemeyer

See #15653 for a blocker follow-up.

Note: See TracTickets for help on using tickets.