#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, #13957, #14563, #14568 |
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)
>
> The patch proposed here develop some general design for dealing with
> continued fractions and solves the issues 1, 2, 3 and 5 (and I hope 4);
> see the discussion below.
>
> 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.value()
> 1/3*sqrt2 + 1/4
> }}}
> 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)
The patch proposed here develop some general design for dealing with
continued fractions and solve all issues above except 4 and 6; see the
discussion below.
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: 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.
--
Comment (by vdelecroix):
The last patch still does not implement a proper function to compute
numerical approximations. It would be interesting to add one...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14567#comment:5>
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.
