#14567: Refactor continued fractions
----------------------------------------------------------------+-----------
Reporter: vdelecroix |
Owner: vdelecroix
Type: enhancement |
Status: needs_review
Priority: major |
Milestone: sage-5.10
Component: number theory |
Resolution:
Keywords: continued fractions, numerical approximation | Work
issues:
Report Upstream: N/A |
Reviewers:
Authors: vdelecroix | Merged
in:
Dependencies: #13213, #13256, #14563 |
Stopgaps:
----------------------------------------------------------------+-----------
Old description:
> Continued fractions (in sage.rings.contfrac) do not do what we expect:
>
> 1. categories are not properly initialized nor used.
> 2. all arithmetic operations go back and forth with the underlying
> rational (there are much more direct solutions for taking the negative,
> inverse and to compare two continued fractions)
> 3. it only deals with rational numbers
> 4. there is no dedicated method for numerical approximations (which is
> one of the first aim of continued fractions)
> 5. there is no bridge with quadratic numbers (see also #11345)
> 6. there is no bridge with words (sage.combinat.words)
> 7. continued fractions are not included in the documentation
>
> The patch proposed here develop some general design for dealing with
> continued fractions and solve all issues above except 6.
>
> With the patch applied we can do
> {{{
> sage: (117/253).continued_fraction()
> [0; 2, 6, 6, 3]
>
> sage: K.<sqrt2> = QuadraticField(2)
> sage: cff = (sqrt2/3 + 1/4).continued_fraction(); cff
> [0; 1, (2, 1, 1, 2, 3, 2, 1, 1, 2, 5, 1, 1, 14, 1, 1, 5)*]
> sage: cff.period()
> (2, 1, 1, 2, 3, 2, 1, 1, 2, 5, 1, 1, 14, 1, 1, 5)
> sage: cff.preperiod()
> (0, 1)
> sage: cff.value()
> 1/3*sqrt2 + 1/4
> sage: cff.n(digits=50)
> 0.72140452079103168293389624140323269285655729179232
>
> sage: cf_pi = continued_fraction(pi)
> [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]
> sage: cf_pi.quotient(1500)
> 1
> }}}
> In particular we solve the question in #11345.
New description:
Continued fractions (in sage.rings.contfrac) do not do what we expect:
1. categories are not properly initialized nor used.
2. all arithmetic operations go back and forth with the underlying
rational (there are much more direct solutions for taking the negative,
inverse and to compare two continued fractions)
3. it only deals with rational numbers
4. there is no dedicated method for numerical approximations (which is
one of the first aim of continued fractions)
5. there is no bridge with quadratic numbers (see also #11345)
6. there is no bridge with words (sage.combinat.words)
7. continued fractions are not included in the documentation
The patch proposed here develop some general design for dealing with
continued fractions and solve all issues above except 6.
With the patch applied we can do
{{{
sage: (117/253).continued_fraction()
[0; 2, 6, 6, 3]
sage: K.<sqrt2> = QuadraticField(2)
sage: cff = (sqrt2/3 + 1/4).continued_fraction(); cff
[0; 1, (2, 1, 1, 2, 3, 2, 1, 1, 2, 5, 1, 1, 14, 1, 1, 5)*]
sage: cff.period()
(2, 1, 1, 2, 3, 2, 1, 1, 2, 5, 1, 1, 14, 1, 1, 5)
sage: cff.preperiod()
(0, 1)
sage: cff.value()
1/3*sqrt2 + 1/4
sage: cff.n(digits=50)
0.72140452079103168293389624140323269285655729179232
sage: cf_pi = continued_fraction(pi)
[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]
sage: cf_pi.quotient(1500)
1
}}}
In particular we solve the question in #11345.
Apply:
* [attachment:trac_14567-continued_fractions.patch]
* [attachment:trac_14567_addon1-fc.patch]
--
Comment (by chapoton):
I have added a small clean-up patch (problems found with pyflakes):
* removed unused import
* removed unused variables
* corrected one wrong variable
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14567#comment:14>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
