Opened 10 years ago
Last modified 8 months ago
#11380 needs_work enhancement
Computing continued fractions on real quadratic fields
Reported by:  mmasdeu  Owned by:  was 

Priority:  minor  Milestone:  sagewishlist 
Component:  number theory  Keywords:  normeuclidean, twostage euclidean, continued_fraction 
Cc:  cremona, sstarosta, lftabera, slelievre  Merged in:  
Authors:  Xevi Guitart, Marc Masdeu  Reviewers:  
Report Upstream:  N/A  Work issues:  Documentation needed 
Branch:  u/chapoton/11380 (Commits, GitHub, GitLab)  Commit:  63081c23b35b8af371b71ca6538fab8c8ce04bf2 
Dependencies:  Stopgaps: 
Description (last modified by )
We have implemented some routines that allow for the computation of continued fractions in real quadratic number fields of class number one. This uses 2stage division chains as defined in G.E.Cooke,"A weakening of the euclidean property for integral domains and applications to algebraic number theory".
The algorithm finds a set of "hyperbolic regions" as described in the above article, large enough so that it covers a fundamental domain. These regions are used to construct 2stage division chains and therefore obtain continued fractions with elements of the ring of integers of the number field.
More information can be found in the preprint posted in the Math Arxiv: http://arxiv.org/abs/1106.0856
Also available as a pipinstallable package that runs on top of Sage:
 github code repo: https://github.com/mmasdeu/twostage
 pip package: https://pypi.org/project/twostage/
Attachments (3)
Change History (28)
Changed 10 years ago by
comment:1 Changed 10 years ago by
 Status changed from new to needs_review
comment:2 Changed 10 years ago by
 Description modified (diff)
comment:3 Changed 10 years ago by
I have added a second patch, which should be applied after the first. This will replace the .py with a .pyx and fix some errors.
I think that this works now as expected. Sorry for the small mess...it's my first ticket :).
comment:4 Changed 10 years ago by
 Cc cremona added
The last attachment contains all the changes and passed all the doctest with Sage 4.7. The first two patches should be disregarded.
comment:5 followup: ↓ 6 Changed 10 years ago by
 Status changed from needs_review to needs_info
I don't think I am qualified to review this since I am not familiar with the algorithm. But I do have one question: Why have you put the new code into a cython (.pyx) file when it does not seem to contain any cython code, only python? (I may be wrong, as I did not read it all). If it is just python, then it can be renamed .py and not included in the module_list.
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to cremona:
I don't think I am qualified to review this since I am not familiar with the algorithm. But I do have one question: Why have you put the new code into a cython (.pyx) file when it does not seem to contain any cython code, only python? (I may be wrong, as I did not read it all). If it is just python, then it can be renamed .py and not included in the module_list.
I updated the patch with the suggested changes. As for the review, during this weekend we plan to upload our preprint to the arxiv, and there you can find the algorithm that we are using explained.
In short, what the only function accessible should do is to return a list of elements of the ring of integers of the number field, so that they are a (terminating) continued fraction for the given element.
comment:7 Changed 10 years ago by
 Description modified (diff)
 Status changed from needs_info to needs_review
comment:8 Changed 10 years ago by
Let me try to help the buildbot:
Apply trac_11380_quadratic_cont_frac.patch
comment:9 Changed 10 years ago by
The current patch is a double patch (read it and you'll see what I mean). Also, I think cremona's question about the .pyx versus .py is a good one.
comment:10 Changed 10 years ago by
Thank you chapoton, kcrisman and cremona for taking a look at this. After kcrisman I am uploading a patch that should work. Any references to the .pyx have been removed (we did that in the second version but apparently it got messed up).
comment:11 Changed 10 years ago by
 Description modified (diff)
for the bot:
Apply trac_11380_quadratic_cont_frac.patch
comment:12 Changed 10 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Documentation needed
This cannot be considered for inclusion into Sage since the file sage/rings/number_field/quadratic_continued_fraction.py
does not have a single docstring or example anywhere.
comment:13 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:14 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:15 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:16 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:17 Changed 7 years ago by
 Branch set to u/chapoton/11380
 Commit set to e11f5e123dfec19fd80e3c508bb666dbc0d132e7
comment:18 Changed 7 years ago by
 Commit changed from e11f5e123dfec19fd80e3c508bb666dbc0d132e7 to 5a474c1cf3c819d5638cee86d34eb7aa09805b12
comment:19 Changed 7 years ago by
 Commit changed from 5a474c1cf3c819d5638cee86d34eb7aa09805b12 to ee8aeb6f358a12a73d3fc5681ee4667db68dbd7c
Branch pushed to git repo; I updated commit sha1. New commits:
ee8aeb6  trac #11380 a little more doc

comment:20 Changed 6 years ago by
 Cc sstarosta added
comment:22 Changed 5 years ago by
 Description modified (diff)
comment:23 Changed 4 years ago by
 Commit changed from ee8aeb6f358a12a73d3fc5681ee4667db68dbd7c to 63081c23b35b8af371b71ca6538fab8c8ce04bf2
Branch pushed to git repo; I updated commit sha1. New commits:
63081c2  Merge branch 'u/chapoton/11380' in 8.0.b9

comment:24 Changed 3 years ago by
 Cc lftabera slelievre added
 Description modified (diff)
 Milestone changed from sage6.4 to sagewishlist
Also available as a pipinstallable package that runs on top of Sage:
 code repo on GitHub: https://github.com/mmasdeu/twostage
 python package on PyPI: https://pypi.org/project/twostage
comment:25 Changed 8 months ago by
 Keywords continued_fraction added; continued fraction removed
First version of the new routines