Opened 13 years ago
Closed 13 years ago
#8017 closed defect (fixed)
incorrect trailing digits for continued fraction
Reported by: | robertwb | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-4.5.3 |
Component: | basic arithmetic | Keywords: | |
Cc: | was | Merged in: | sage-4.5.3.alpha0 |
Authors: | Robert Bradshaw | Reviewers: | Paul Zimmermann |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
continued_fraction(sqrt(2)) [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
Followup to and depends on #5107, which documents the function better.
Attachments (4)
Change History (16)
Changed 13 years ago by
Attachment: | 8017-cont-frac.patch added |
---|
comment:1 Changed 13 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 13 years ago by
Cc: | was added |
---|
comment:3 Changed 13 years ago by
Status: | needs_review → needs_info |
---|
Robert, this seems to be great work! However a small question: for *exact* symbolic input, the truncated continued fraction should not depend on the initial floating-point approximation, and should be a truncation of the (finite or infinite) continued fraction:
sage: continued_fraction(22/7,bits=4) [3, 4] sage: continued_fraction(22/7,bits=5) [3, 8]
I guess the above should give instead:
sage: continued_fraction(RealIntervalField(4)(22/7)) [3] sage: continued_fraction(RealIntervalField(5)(22/7)) [3]
Can the same problem happen with say sqrt(2), or is it only for rationals?
Changed 13 years ago by
Attachment: | 8017-contfrac-referee-fixes.patch added |
---|
comment:4 Changed 13 years ago by
Status: | needs_info → needs_review |
---|
Thank you for looking at this. As you can probably tell, the current behavior really bothers me ;). I've fixed the case above (yes, it only impacted rationals).
comment:5 Changed 13 years ago by
Status: | needs_review → needs_work |
---|
while I'm running the doctests, a few comments: (1) maybe the documentation should say that the
terms of the truncated continued fraction are (now) guaranteed exact (using interval arithmetic);
(2) If nterms is given, the precision is increased until the specified number of terms can be computed
: if possible, for example 22/7 will give only two terms.
I also suggest giving an additional example showing that we can give as input a floating-point interval, and the difference with a floating-point number (where initial rounding error can give an incorrect result):
sage: continued_fraction(RealField(39)(e)) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 2] sage: continued_fraction(RealIntervalField(39)(e)) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10]
In the meantime the doctests finished, and I get two failures:
sage -t core2/devel/sage-8017/sage/combinat/words/word_generators.py # 1 doctests failed sage -t core2/devel/sage-8017/sage/tests/book_stein_ent.py # 13 doctests failed
comment:6 Changed 13 years ago by
Status: | needs_work → needs_review |
---|
comment:7 Changed 13 years ago by
Authors: | → Robert Bradshaw |
---|---|
Reviewers: | → Paul Zimmermann |
Status: | needs_review → positive_review |
positive review, good work, Robert! However I see as a side effect you had to change the doctests in William's book, which has the consequence that those examples will not work any more as in the book (but better now). This is a concern for me with the book we wrote about Sage (btw, the doctest of the number theory chapter is ready for review, see #9395).
Paul
Changed 13 years ago by
Attachment: | 8017-contfrac-referee2.patch added |
---|
comment:8 Changed 13 years ago by
Thanks for being so quick to look at this after such a long wait. Yes, I was thinking about this when I made these changes. The answers are not substantially different, and should be clear to any user that the current behavior is correct (e.g. by computing things out to higher precision or consulting external sources).
Most importantly, the commands used are not broken or semantically different, which would be really bad. I refreshed the patch just inserting a little note about the change (and, of course, it will be fully recorded in the revision control system).
comment:9 Changed 13 years ago by
Status: | positive_review → needs_info |
---|
Should the release manager merge all three patches? By the way, the first patch is missing a Mercurial header and the second a descriptive commit string.
comment:10 Changed 13 years ago by
Status: | needs_info → needs_review |
---|
I have folded all three patches into 8017-all.patch, apply that one.
comment:11 Changed 13 years ago by
Status: | needs_review → positive_review |
---|
comment:12 Changed 13 years ago by
Merged in: | → sage-4.5.3.alpha0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
This does change the definition from "continued fraction expansion of a real approximation" to "truncation of continued fraction expansion." It also adds an nterms option to compute a specified number of terms.