#14567: Refactor continued fractions
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: number theory | Resolution:
Keywords: continued | Merged in:
fractions, numerical | Reviewers: Ralf Stephan, Thierry
approximation | Monteil
Authors: Vincent Delecroix | Work issues:
Report Upstream: N/A | Commit:
Branch: | b57017903cfe976bc3c8f1adda47127467b2f73c
u/vdelecroix/14567 | Stopgaps:
Dependencies: #13213, #13256, |
#14563 |
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_work => needs_review
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.
>
> Apply:
> * [attachment:trac_14567-continued_fractions.patch]
> * [attachment:trac_14567_addon1-fc.patch]
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.
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
sage: cf_fib = continued_fraction(words.FibonacciWord([1,2]))
sage: cf_fib
[1; 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2...]
sage: cf_fib.n(digits=42)
1.38795458796714233691931385987318547787815
}}}
In particular we solve the question in #11345.
--
Comment:
Non fast forward commit (I have just one commit from 6.2.rc0 now).
This new implementation is cleaner and needs review !
I guess we might deprecate `CFF` in an other ticket (but I will not do
it).
--
Ticket URL: <http://trac.sagemath.org/ticket/14567#comment:42>
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.
For more options, visit https://groups.google.com/d/optout.
