Opened 8 years ago

Last modified 5 months ago

#11380 needs_work enhancement

Computing continued fractions on real quadratic fields

Reported by: mmasdeu Owned by: was
Priority: minor Milestone: sage-wishlist
Component: number theory Keywords: norm-euclidean, two-stage 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) Commit: 63081c23b35b8af371b71ca6538fab8c8ce04bf2
Dependencies: Stopgaps:

Description (last modified by slelievre)

We have implemented some routines that allow for the computation of continued fractions in real quadratic number fields of class number one. This uses 2-stage 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 2-stage 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 pip-installable package that runs on top of Sage:

Attachments (3)

trac_11380_cont_frac_quadratic.patch (20.0 KB) - added by mmasdeu 8 years ago.
First version of the new routines
trac_11380_cont_frac_quadratic_2.patch (31.1 KB) - added by mmasdeu 8 years ago.
Second version
trac_11380_quadratic_cont_frac.patch (20.3 KB) - added by mmasdeu 7 years ago.
To be used alone

Download all attachments as: .zip

Change History (27)

Changed 8 years ago by mmasdeu

First version of the new routines

comment:1 Changed 8 years ago by mmasdeu

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by mmasdeu

  • Description modified (diff)

Changed 8 years ago by mmasdeu

Second version

comment:3 Changed 8 years ago by mmasdeu

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 8 years ago by mmasdeu

  • 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 follow-up: Changed 8 years ago by cremona

  • 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 8 years ago by mmasdeu

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 8 years ago by mmasdeu

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

comment:8 Changed 7 years ago by chapoton

Let me try to help the buildbot:

Apply trac_11380_quadratic_cont_frac.patch

comment:9 Changed 7 years ago by kcrisman

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.

Changed 7 years ago by mmasdeu

To be used alone

comment:10 Changed 7 years ago by mmasdeu

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 7 years ago by chapoton

  • Description modified (diff)

for the bot:

Apply trac_11380_quadratic_cont_frac.patch

comment:12 Changed 7 years ago by davidloeffler

  • 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 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:15 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:17 Changed 4 years ago by chapoton

  • Branch set to u/chapoton/11380
  • Commit set to e11f5e123dfec19fd80e3c508bb666dbc0d132e7

New commits:

1313d05Trac #11380: Added routines to compute continued fractions in real
e11f5e1trac #11380 code in pep8 standard

comment:18 Changed 4 years ago by git

  • Commit changed from e11f5e123dfec19fd80e3c508bb666dbc0d132e7 to 5a474c1cf3c819d5638cee86d34eb7aa09805b12

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

5f3ef20Merge branch 'u/chapoton/11380' of ssh://trac.sagemath.org:22/sage into 11380
5a474c1trac #11380 restore broken things

comment:19 Changed 4 years ago by git

  • Commit changed from 5a474c1cf3c819d5638cee86d34eb7aa09805b12 to ee8aeb6f358a12a73d3fc5681ee4667db68dbd7c

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

ee8aeb6trac #11380 a little more doc

comment:20 Changed 3 years ago by sstarosta

  • Cc sstarosta added

comment:21 Changed 3 years ago by vdelecroix

  • Authors changed from Xevi Guitart and Marc Masdeu to Xevi Guitart, Marc Masdeu

typo in the Authors field

comment:22 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:23 Changed 18 months ago by git

  • Commit changed from ee8aeb6f358a12a73d3fc5681ee4667db68dbd7c to 63081c23b35b8af371b71ca6538fab8c8ce04bf2

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

63081c2Merge branch 'u/chapoton/11380' in 8.0.b9

comment:24 Changed 5 months ago by slelievre

  • Cc lftabera slelievre added
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-wishlist

Also available as a pip-installable package that runs on top of Sage:

Note: See TracTickets for help on using tickets.