#14567 closed enhancement (fixed)
Refactor continued fractions
Reported by:  vdelecroix  Owned by:  vdelecroix 

Priority:  major  Milestone:  sage6.5 
Component:  number theory  Keywords:  continued fractions, numerical approximation 
Cc:  tmonteil, slabbe, Fougeroc  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Ralf Stephan, Thierry Monteil 
Report Upstream:  N/A  Work issues:  
Branch:  ec4a4ba (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #13213, #13256, #14563  Stopgaps: 
Description (last modified by )
Continued fractions (in sage.rings.contfrac) do not do what we expect:
 categories are not properly initialized nor used.
 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)
 it only deals with rational numbers
 there is no dedicated method for numerical approximations (which is one of the first aim of continued fractions)
 there is no bridge with quadratic numbers (see also #11345)
 there is no bridge with words (sage.combinat.words)
 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.
Attachments (3)
Change History (71)
comment:1 Changed 8 years ago by
 Dependencies changed from #13213, #13957, #14563 to #13213, #13957, #14563, #14568
 Description modified (diff)
comment:2 Changed 8 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 8 years ago by
 Description modified (diff)
comment:4 Changed 8 years ago by
 Description modified (diff)
comment:5 Changed 8 years ago by
 Description modified (diff)
The last patch still does not implement a proper function to compute numerical approximations. It would be interesting to add one...
comment:6 Changed 8 years ago by
 Dependencies changed from #13213, #13957, #14563, #14568 to #13213, #13256, #14563
comment:7 Changed 8 years ago by
The patch modifies the output of continued_fraction and hence some tests in sage.books.book_stein_ent
. We have to be careful with changes that concern examples from a book. See the related discussion on sagedevel
comment:8 Changed 8 years ago by
 Description modified (diff)
comment:9 followup: ↓ 10 Changed 8 years ago by
 Status changed from needs_review to needs_work
instead of
doctest:2057: UserWarning
you should use
doctest:...: UserWarning
because the numbers can change
There are some other doctests failing due to the change of output string, please correct them
comment:10 in reply to: ↑ 9 Changed 8 years ago by
Replying to chapoton:
instead of
doctest:2057: UserWarningyou should use
doctest:...: UserWarningbecause the numbers can change
Many thanks for that suggestion (it actually happens for me several times).
There are some other doctests failing due to the change of output string, please correct them
The ticket is updated.
comment:11 Changed 8 years ago by
 Status changed from needs_work to needs_review
comment:12 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to failing doctest
A doctest still fails.
comment:13 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues failing doctest deleted
comment:14 followup: ↓ 15 Changed 8 years ago by
 Description modified (diff)
I have added a small cleanup patch (problems found with pyflakes):
 removed unused import
 removed unused variables
 corrected one wrong variable
comment:15 in reply to: ↑ 14 Changed 8 years ago by
Replying to chapoton:
I have added a small cleanup patch (problems found with pyflakes):
 removed unused import
 removed unused variables
 corrected one wrong variable
Thanks. I am now confident that the patch is perfect!
Changed 8 years ago by
comment:16 Changed 8 years ago by
 Cc slabbe added
comment:17 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:18 followup: ↓ 19 Changed 7 years ago by
What is the status of this patch? I need it for a server that I am running for others. It applies cleanly to only sage5.9 and sage5.10. :(
Can you rebase it to 5.12 or 5.13? The size of the hunk that fails (in continued_fractions.py
) is too large, and so I do not want to mess up in modifying the code.
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 7 years ago by
Replying to ppurka:
What is the status of this patch? I need it for a server that I am running for others. It applies cleanly to only sage5.9 and sage5.10. :(
Can you rebase it to 5.12 or 5.13? The size of the hunk that fails (in
continued_fractions.py
) is too large, and so I do not want to mess up in modifying the code.
Hi. I am waiting for the review. I know that Thierry has many remarks (we already discussed some in private) but I can do a rebase in order that it applies on 5.13 tomorrow during the Sage day in Paris. Do you need a patch or git branch is fine for you ?
comment:20 in reply to: ↑ 19 Changed 7 years ago by
Replying to vdelecroix:
Hi. I am waiting for the review. I know that Thierry has many remarks (we already discussed some in private) but I can do a rebase in order that it applies on 5.13 tomorrow during the Sage day in Paris. Do you need a patch or git branch is fine for you ?
Thanks! Either patch or git branch is fine with me. I can recreate a patch from the git branch, if needed.
Changed 7 years ago by
comment:21 followup: ↓ 22 Changed 7 years ago by
I uploaded a patch which applies on 5.12.rc0. I will now create a branch.
comment:22 in reply to: ↑ 21 Changed 7 years ago by
Replying to vdelecroix:
I uploaded a patch which applies on 5.12.rc0. I will now create a branch.
Thanks! Strangely, it applies to 5.13.beta3, but not to 6.0 (git branch).
comment:23 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:24 Changed 7 years ago by
You have to use patch
with the l
option, then it succeeds. I will open a git branch.
comment:25 Changed 7 years ago by
 Branch set to u/rws/ticket/14567
 Created changed from 05/11/13 15:09:00 to 05/11/13 15:09:00
 Modified changed from 02/12/14 10:18:47 to 02/12/14 10:18:47
comment:26 Changed 7 years ago by
 Commit set to af5fa7da73481842c0b224d5b387ff1f7597947e
Rebased on 6.2.beta2, tests fine. The docs do not build, however, because of a dangling ref in database_sloane.
New commits:
af5fa7d  ticket 14567

comment:27 Changed 7 years ago by
 Commit changed from af5fa7da73481842c0b224d5b387ff1f7597947e to 7e0af698f04d10ca778db740b01e458c0de783b0
Branch pushed to git repo; I updated commit sha1. New commits:
7e0af69  Trac #14567: reviewer's patch: enable docbuild

comment:28 Changed 7 years ago by
 Reviewers set to Ralf Stephan
 Status changed from needs_review to positive_review
I like the result a lot with its modular structure. One even can create a CFF given the preperiod and the periodic part, they need to be at least pairs however. But this should not hold back this ticket, because there is an easy workaround.
comment:29 Changed 7 years ago by
 Status changed from positive_review to needs_work
Ralf, commit 7e0af96 is the wrong way to do fix it (take a look at the compiled documentation). Instead you should have removed the second colon from the EXAMPLES::
. In other words, it should be formatted like this:
EXAMPLES: Some docstring talking about the example:: sage: 2 + 2 4 Some more docstrings:: sage: 4  2 2
Thierry (or Vincent), did you have any comments about the current state of the branch?
comment:30 Changed 7 years ago by
 Commit changed from 7e0af698f04d10ca778db740b01e458c0de783b0 to fb96ac7c8eae9834e3513c2fbd9abd450faa58c0
Branch pushed to git repo; I updated commit sha1. New commits:
fb96ac7  Fix previous patch

comment:31 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:32 Changed 7 years ago by
Hi, sorry for not talking on this before. I started to review this patch a few months ago but did not finished. There are a lot of issues with CFF. I did not switch to the new layout now, so, if the code did not change too much, my comments should be still valid, I will post a few of them this week end. Again, sorry for the delay.
Changed 7 years ago by
comment:33 followup: ↓ 37 Changed 7 years ago by
 Reviewers changed from Ralf Stephan to Ralf Stephan, Thierry Monteil
This review is not polished, but i provide it as is, so that we can discuss. I also uploaded a (beginning of a) patch containing minor modifications, even if this corresponds to the old workflow.
CFF
is not fully autonomous and behaves like an overlay over other Sage
fields, thus sacrificing reliability over expressivity.
sage: a = CFF(0.1) sage: a.value() 1/10
vs
sage: a = CFF(0.1+sqrt(2)) sage: a.value() sqrt(2) + 0.100000000000000
Hence the mess:
sage: a = CFF(0.1+sqrt(2)) sage: b = CFF(0.1) + CFF(sqrt(2)) sage: a == b True
but
sage: a [1; 1, 1, 17, 11, 3, 1, 8, 2, 1, 2, 2, 281, 1, 10, 3, 2, 3, 21, 5, ...] sage: b [1; (1, 1, 17, 11, 3, 1, 8, 2, 1, 2, 2, 282, 2, 2, 1, 2, 8, 1, 3, 11, 17, 1, 1, 2, 3, 5, 2, 10, 1, 5, 1, 69, 1, 5, 1, 10, 2, 5, 3, 2)*]
I have not much problems with this overlay design as long as it is clearly stated and consistent.
Note that this behaviour is not uniform, since CFF(a).value()
is sometimes not
equal to a
, but this is not clear when.
 << Return the value of "self" (the number from which it was built). >>  << Return the value of "self" as a quadratic number (with square free discriminant). >>
This is not the role of CFF
to canonicalize Sage real numbers, though one
could imagine such a class/function GoodRealField
.
sage: CFF(sqrt(2)) [1; (2)*] sage: CFF(sqrt(2)).value() sqrt2 sage: CFF(0.1) [0; 10] sage: CFF(0.1).value() 1/10 sage: CFF(pi) [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...] sage: CFF(pi).value() pi sage: (2^(1/3)).parent() Symbolic Ring sage: CFF(2^(1/3)).value().parent() Algebraic Real Field
Another consequence of the overlay structure is that the inverse of a continued fraction is not as expected (the inverse should only shift the sequence of partial quotients):
sage: a = CFF(pi+0.1) ; a [3; 4, 7, 5, 2, 3, 2, 1, 1, 1, 4, 1, 4, 33, 4, 2, 6, 10, 3, 1, ...] sage: ~a [0; 3, 4, 7, 5, 2, 3, 2, 1, 1, 1, 4, 1, 4, 33, 4, 4, 1, 1, 1, ...]
I do understand that this may be a transitional behaviour. But how to tell that to sage users ?
I see two ways:
 be always an "overlay field"
 restrict the code to words (cf your issue 6) you really handle (rationals and quadratic irrationals, corresponding to finite and ultimately periodic words) ?
Perhaps a solution is to have two very distinct classes (with conversions) ?
Another issue is:
sage: CFF.is_exact() True
I disagree with that statement, since there are approximate elements in CFF,
for example CFF(pi+0.1)
.
Problems with SR
:
sage: sqrt(2) == QQbar(sqrt(2)) True sage: CFF(sqrt(2)) == CFF(QQbar(sqrt(2))) Wait for a long time... sage: CFF(sqrt(2)).value().parent() Number Field in sqrt2 with defining polynomial x^2  2 sage: CFF(sqrt(2)).value() == CFF(QQbar(sqrt(2))).value() False
Transitivity of equality:
sage: bool(CFF(sqrt(2)).value() == sqrt(2)) True sage: bool(sqrt(2)) == sqrt(QQbar(2)) True sage: CFF(sqrt(2)).value() == sqrt(QQbar(2)) False
in _element_constructor_()
 ``nterms``  integer (optional) ??? is that an old remaining thing ?  ``check``  boolean (optional)  whether or not we check the "the" what ?
When you test whether an element of SR
is a real number, you use RIF(x)
.
Why not using x.is_real()
(and make this method more reliable if needed) ?
Another problem:
sage: a = RDF(0.1) sage: CFF(a) [0]
The reason is :
sage: (1/RIF(RDF(0.1))).unique_floor() ValueError: interval does not have a unique floor
In the doc: "It is quite remarkable that".
Add : " any real number admits a unique continued fraction expansion"
"It is also possible to create a continued fraction from a list of digits::"
I would propose : "from a list of numbers corresponding to its partial quotients."
"For quadratic numbers, the syntax is quite similar and the digits are represented as a pair of tuples, the preperiod and the period::"
Again, "digits" vs "partial quotients"
Another problem:
sage: cf = CFF([(1,2,3),(1,2,4)]); cf.value() 1/86*sqrt229 + 139/86 sage: sqrt229 .... NameError: name 'sqrt229' is not defined
CFF
outputs an element of a quadratic field that can not be used
furthermore. Of course, one can get it back with cf.parent().gen()
. Perhaps
inject those variables ?
"two_last_convergents" > "last_two_convergents"
_pn
and _qn
looks good for internal variables, but i would suggest to
replace pn()
and qn()
methods by numerator()
and denominator()
to stay
consistent with rationals.
In the _mpfr_
method: "It is guaranteed that the result is exact"
Floating point number are not exact, perhaps "accurate" is a better word ?
comment:34 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:35 Changed 7 years ago by
 Branch changed from u/rws/ticket/14567 to u/vdelecroix/14567
 Commit changed from fb96ac7c8eae9834e3513c2fbd9abd450faa58c0 to 6a2d6aa35d52acf73c1e6f1d1eefe3e037486738
comment:36 Changed 7 years ago by
 Commit changed from 6a2d6aa35d52acf73c1e6f1d1eefe3e037486738 to 8fbf106cbde07fed9c3f3ea2b32c9309185062af
comment:37 in reply to: ↑ 33 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to tmonteil:
CFF
is not fully autonomous and behaves like an overlay over other Sage fields, thus sacrificing reliability over expressivity.
agreed. There is no transformation on input now. Most problem disappear. The only trouble might be with floating point as I decided to first convert the input into a rational. Note however that
sage: RR.random_element() in QQ True
I have not much problems with this overlay design as long as it is clearly stated and consistent.
It is !
Another issue is:
sage: CFF.is_exact() TrueI disagree with that statement, since there are approximate elements in CFF, for example
CFF(pi+0.1)
.
I do not want to make CFF inexact. The trouble comes from the unstability of CFF... If you want a friendly CFF you either have to rebuild the symbolic ring or do with it.
in
_element_constructor_()
 ``nterms``  integer (optional) ??? is that an old remaining thing ?  ``check``  boolean (optional)  whether or not we check the "the" what ?
This is now removed
When you test whether an element of
SR
is a real number, you useRIF(x)
. Why not usingx.is_real()
(and make this method more reliable if needed) ?
you can not believe in is_real
but I used it.
Another problem:
sage: a = RDF(0.1) sage: CFF(a) [0]The reason is :
sage: (1/RIF(RDF(0.1))).unique_floor() ValueError: interval does not have a unique floor
It is now correct.
sage: continued_fraction(0.1) [0; 10]
In the doc: "It is quite remarkable that".
Add : " any real number admits a unique continued fraction expansion"
done
[...]
I would propose : "from a list of numbers corresponding to its partial quotients."
All occurrences of digits are removed and replaced by partial quotients.
Another problem:
sage: cf = CFF([(1,2,3),(1,2,4)]); cf.value() 1/86*sqrt229 + 139/86 sage: sqrt229 .... NameError: name 'sqrt229' is not defined
I agree. It is quite hard to make it works. I only documented how to do
that in the method value
.
"two_last_convergents" > "last_two_convergents"
done
_pn
and_qn
looks good for internal variables, but i would suggest to replacepn()
andqn()
methods bynumerator()
anddenominator()
to stay consistent with rationals.
done
In the
_mpfr_
method: "It is guaranteed that the result is exact"Floating point number are not exact, perhaps "accurate" is a better word ?
done
comment:38 Changed 7 years ago by
 Cc Fougeroc added
comment:39 Changed 7 years ago by
 Commit changed from 8fbf106cbde07fed9c3f3ea2b32c9309185062af to 43de3213c4158fa2e48675c24d1ed552fd4a4d65
Branch pushed to git repo; I updated commit sha1. New commits:
8dfcac0  ticket 14567

91ce0e6  Trac #14567: reviewer's patch: enable docbuild

83e4eff  Fix previous patch

25b49ca  fix import statements in sage.rings.all

94104e2  move farey to continued_fractions

07d9a29  cont_frac: pn > numberator, qn > denominator

b871cc1  update the code with respect to reviewer remarks

66f46f6  Merge branch 'develop' into 14567continued_fractions

43de321  Merge branch 'u/vdelecroix/14567' of trac.sagemath.org:sage into 14567continued_fractions

comment:40 Changed 7 years ago by
 Status changed from needs_review to needs_work
Hello,
I am still working on this.
Firstly, it is easy to implement a class for continued fractions given by an infinite expansion... so I propose to include it in that ticket.
Secondly, I have a big open question: what should be the parent (if any) of a continued fraction? As Thierry M. already mentioned, the CFF
class does not fit very well.
Vincent
comment:41 Changed 7 years ago by
 Commit changed from 43de3213c4158fa2e48675c24d1ed552fd4a4d65 to b57017903cfe976bc3c8f1adda47127467b2f73c
Branch pushed to git repo; I updated commit sha1. New commits:
b570179  trac 14567: continued fraction (based on 6.2.rc0)

comment:42 Changed 7 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
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).
comment:43 Changed 7 years ago by
For the record it is necessary to
sage b make docclean make doc
to build the documentation. sage docbuild
will not suffice (fails).
comment:44 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:45 Changed 7 years ago by
 Status changed from needs_review to needs_work
patchbot:
sage t long src/sage/combinat/words/finite_word.py # 1 doctest failed sage t long src/sage/combinat/words/word_generators.py # 23 doctests failed sage t long src/doc/en/prep/Calculus.rst # Timed out sage t long src/sage/rings/rational.pyx # 2 doctests failed
comment:46 Changed 7 years ago by
 Commit changed from b57017903cfe976bc3c8f1adda47127467b2f73c to da8a52b074d80e5de286e9923fbdb780e14ce347
comment:47 Changed 7 years ago by
 Status changed from needs_work to needs_review
Thanks (a bug in plot and a bug in words).
Now the tests pass.
Vincent
comment:48 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to doctest continuation
you need to use the new doc continuation style ...:
(see patchbot report)
comment:49 Changed 7 years ago by
 Branch changed from u/vdelecroix/14567 to public/ticket/14567
 Commit changed from da8a52b074d80e5de286e9923fbdb780e14ce347 to 62fdcda1159d16bbb4b4a72b94b3c9c555ad9238
 Status changed from needs_work to needs_review
comment:50 Changed 7 years ago by
Thanks!
PS Note: there is no need to do a merge as in your commit 7da398e. The option I use to pull a branch from track is
git fetch trac thebranchIneed git checkout b agoodname FETCH_HEAD
comment:51 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:52 Changed 6 years ago by
What remains to be done here to give positive review?
comment:53 Changed 6 years ago by
 Commit changed from 62fdcda1159d16bbb4b4a72b94b3c9c555ad9238 to 925deeb009963f73da4f3fb4cb49f53bbb366ca8
Branch pushed to git repo; I updated commit sha1. New commits:
925deeb  14567: reviewer's patch: add early example of continued_fraction_list

comment:54 Changed 6 years ago by
 Status changed from needs_review to positive_review
Branch passes make ptestlong
. I added an early example of continued_fraction_list
to the docs for convenience. I think the issue with exactifying reals should be addressed with a GoodRealField
as mentioned in comment:33, anyway a different ticket, as are extensions to symbolic expressions.
comment:55 Changed 6 years ago by
Thanks.
There are changes that affect two of William's books. I sent him an email (cc'ed in sagedevel): see this thread.
Vincent
comment:56 Changed 6 years ago by
 Work issues doctest continuation deleted
comment:57 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
comment:58 Changed 6 years ago by
 Commit changed from 925deeb009963f73da4f3fb4cb49f53bbb366ca8 to ec4a4baa149a9b9e74dc32d25745b81059af2e6b
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
ec4a4ba  trac #14567: fix doctest

comment:59 followup: ↓ 60 Changed 6 years ago by
 Status changed from needs_review to positive_review
Ralf,
the one line you add to the file was wrong. I just replace it.
I guess we should close the ticket has nobody answered on the sagedevel thread since a month now.
Vincent
comment:60 in reply to: ↑ 59 Changed 6 years ago by
Replying to vdelecroix:
the one line you add to the file was wrong. I just replace it.
Oh well, thanks.
comment:61 Changed 6 years ago by
Note: merge cleanly on sage6.5.beta6 and tests pass in sage/rings
, sage/modular
and sage/tests
!
comment:62 Changed 6 years ago by
 Branch changed from public/ticket/14567 to ec4a4baa149a9b9e74dc32d25745b81059af2e6b
 Resolution set to fixed
 Status changed from positive_review to closed
comment:63 Changed 6 years ago by
 Commit ec4a4baa149a9b9e74dc32d25745b81059af2e6b deleted
Hey, I just hit an annoying case...
sage: continued_fraction_list(1.575709393346379) Error in lines 11 Traceback (most recent call last): ... ValueError: does not know how to compute the continued fraction of 1.57570939334638
However,
sage: continued_fraction_list(0 + 1.575709393346379) [1, 1, 1, 2, 1, 4, 18, 1, 5, 2, 22909319]
The problem is that RealLiteral? and continued fractions no longer work together...
comment:64 followup: ↓ 65 Changed 6 years ago by
Indeed... did you open a ticket?
comment:65 in reply to: ↑ 64 ; followup: ↓ 66 Changed 6 years ago by
comment:66 in reply to: ↑ 65 ; followup: ↓ 67 Changed 6 years ago by
Indeed... did you open a ticket?
No, can you?
Ping  I don't quite know what the issue is but hopefully a ticket can be opened.
comment:67 in reply to: ↑ 66 Changed 6 years ago by
comment:68 Changed 5 years ago by
See #20012 for really deprecating CFF
(ContinuedFractionField
).
The ticket is not yet finished but the review may start (all test pass on my computer... waiting for patchbot). Here are some questions I am not sure how to deal about.
_mpfr_
in sage.rings.continued_fraction_element`) ?_integer_
, QQ has_rational_
and RR has_mpfr_
, ...). For now it is simplycontinued_fraction
as the user may prefermy_number.continued_fraction()
toCFF(my_number)
.sage.rings.arith
should move tosage.rings.continued_fraction_field
(I think I do prefersage.rings.continued_fractions
tosage.rings.continued_fraction_field
...).