Computing continued fractions on real quadratic fields

[mmasdeu]

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:

• github code repo: https://github.com/mmasdeu/twostage
• pip package: https://pypi.org/project/twostage/

CC: @JohnCremona @staroste @lftabera @slel

Component: number theory

Keywords: norm-euclidean, two-stage euclidean, continued_fraction

Work Issues: Documentation needed

Author: Xevi Guitart, Marc Masdeu

Branch/Commit: u/chapoton/11380 @ 63081c2

Issue created by migration from https://trac.sagemath.org/ticket/11380

[mmasdeu]

Attachment: trac_11380_cont_frac_quadratic.patch.gz

First version of the new routines

[mmasdeu]

Description changed:

--- 
+++ 
@@ -1,5 +1,3 @@
 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.
-
-This is a

[mmasdeu]

Second version

[mmasdeu]

comment:3

Attachment: trac_11380_cont_frac_quadratic_2.patch.gz

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

[mmasdeu]

comment:4

The last attachment contains all the changes and passed all the doctest with Sage 4.7. The first two patches should be disregarded.

[JohnCremona]

comment:5

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.

[mmasdeu]

comment:6

Replying to @JohnCremona:

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.

[mmasdeu]

Description changed:

--- 
+++ 
@@ -1,3 +1,6 @@
 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
+

[fchapoton]

comment:8

Let me try to help the buildbot:

Apply trac_11380_quadratic_cont_frac.patch

[kcrisman]

comment:9

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.

[mmasdeu]

To be used alone

[mmasdeu]

comment:10

Attachment: trac_11380_quadratic_cont_frac.patch.gz

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

[fchapoton]

Description changed:

--- 
+++ 
@@ -4,3 +4,6 @@

 More information can be found in the preprint posted in the Math Arxiv: http://arxiv.org/abs/1106.0856

+
+Apply trac_11380_quadratic_cont_frac.patch
+

[fchapoton]

comment:11

for the bot:

Apply trac_11380_quadratic_cont_frac.patch

[11d1fc49-71a1-44e1-869f-76be013245a0]

comment:12

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.

[11d1fc49-71a1-44e1-869f-76be013245a0]

Work Issues: Documentation needed

[fchapoton]

New commits:

1313d05	Trac #11380: Added routines to compute continued fractions in real
e11f5e1	trac #11380 code in pep8 standard

[fchapoton]

Branch: u/chapoton/11380

[fchapoton]

Commit: e11f5e1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e11f5e1 to 5a474c1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ee8aeb6

trac #11380 a little more doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5a474c1 to ee8aeb6

[videlec]

comment:21

typo in the Authors field

[videlec]

Changed author from Xevi Guitart and Marc Masdeu to Xevi Guitart, Marc Masdeu

[fchapoton]

Description changed:

--- 
+++ 
@@ -5,5 +5,4 @@
 More information can be found in the preprint posted in the Math Arxiv: http://arxiv.org/abs/1106.0856

-Apply trac_11380_quadratic_cont_frac.patch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

63081c2

Merge branch 'u/chapoton/11380' in 8.0.b9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ee8aeb6 to 63081c2

[slel]

Description changed:

--- 
+++ 
@@ -4,5 +4,7 @@

 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:
+- github code repo: https://github.com/mmasdeu/twostage
+- pip package: https://pypi.org/project/twostage/

-

[slel]

comment:24

Also available as a pip-installable 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

[fchapoton]

Changed keywords from norm-euclidean, two-stage euclidean, continued fraction to norm-euclidean, two-stage euclidean, continued_fraction