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:

Status badges

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)

8017-cont-frac.patch (22.1 KB) - added by robertwb 13 years ago.
8017-contfrac-referee-fixes.patch (783 bytes) - added by robertwb 13 years ago.
8017-contfrac-referee2.patch (5.7 KB) - added by robertwb 13 years ago.
8017-all.patch (26.7 KB) - added by robertwb 13 years ago.
apply only this patch

Download all attachments as: .zip

Change History (16)

Changed 13 years ago by robertwb

Attachment: 8017-cont-frac.patch added

comment:1 Changed 13 years ago by robertwb

Status: newneeds_review

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.

comment:2 Changed 13 years ago by robertwb

Cc: was added

comment:3 Changed 13 years ago by zimmerma

Status: needs_reviewneeds_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 robertwb

comment:4 Changed 13 years ago by robertwb

Status: needs_infoneeds_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 zimmerma

Status: needs_reviewneeds_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 robertwb

Status: needs_workneeds_review

comment:7 Changed 13 years ago by zimmerma

Authors: Robert Bradshaw
Reviewers: Paul Zimmermann
Status: needs_reviewpositive_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 robertwb

comment:8 Changed 13 years ago by robertwb

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 mpatel

Status: positive_reviewneeds_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.

Changed 13 years ago by robertwb

Attachment: 8017-all.patch added

apply only this patch

comment:10 Changed 13 years ago by robertwb

Status: needs_infoneeds_review

I have folded all three patches into 8017-all.patch, apply that one.

comment:11 Changed 13 years ago by robertwb

Status: needs_reviewpositive_review

comment:12 Changed 13 years ago by mpatel

Merged in: sage-4.5.3.alpha0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.