Opened 13 years ago

Closed 13 years ago

# incorrect trailing digits for continued fraction

Reported by: Owned by: robertwb AlexGhitza major sage-4.5.3 basic arithmetic was sage-4.5.3.alpha0 Robert Bradshaw Paul Zimmermann N/A

### 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.

### comment:1 Changed 13 years ago by robertwb

Status: new → needs_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:3 Changed 13 years ago by zimmerma

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?

### comment:4 Changed 13 years ago by robertwb

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 zimmerma

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 robertwb

Status: needs_work → needs_review

### comment:7 Changed 13 years ago by zimmerma

Authors: → Robert Bradshaw → Paul Zimmermann 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

### 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_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.

### Changed 13 years ago by robertwb

apply only this patch

### comment:10 Changed 13 years ago by robertwb

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 robertwb

Status: needs_review → positive_review

### comment:12 Changed 13 years ago by mpatel

Merged in: → sage-4.5.3.alpha0 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.