Refactor continued fractions

[videlec]

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 Period method for quadratic irrationals #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.

Depends on #13213
Depends on #13256
Depends on #14563

CC: @sagetrac-tmonteil @seblabbe @sagetrac-Fougeroc

Component: number theory

Keywords: continued fractions, numerical approximation

Author: Vincent Delecroix

Branch: ec4a4ba

Reviewer: Ralf Stephan, Thierry Monteil

Issue created by migration from https://trac.sagemath.org/ticket/14567

[videlec]

Changed dependencies from #13213, #13957, #14563 to #13213, #13957, #14563, #14568

[videlec]

comment:2

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.

• How to cleanly implement numerical approximations of continued fractions (see the current (stupid) implementation of _mpfr_ in sage.rings.continued_fraction_element`) ?
• What method name do we choose for conversion to continued fractions ? (ZZ has _integer_, QQ has _rational_ and RR has _mpfr_, ...). For now it is simply continued_fraction as the user may prefer my_number.continued_fraction() to CFF(my_number).
• The link with words is not yet done and perhaps should be delayed to another ticket as the patch is yet 2500 lines long.
• some of the stuff about continued fractions in sage.rings.arith should move to sage.rings.continued_fraction_field (I think I do prefer sage.rings.continued_fractions to sage.rings.continued_fraction_field...).
• I did not check what are the Pari's fonctionnalities that may be used here

[videlec]

comment:5

The last patch still does not implement a proper function to compute numerical approximations. It would be interesting to add one...

[videlec]

Changed dependencies from #13213, #13957, #14563, #14568 to #13213, #13256, #14563

[videlec]

comment:7

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 sage-devel

[fchapoton]

comment:9

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

[videlec]

comment:10

Replying to @fchapoton:

instead of

doctest:2057: UserWarning

you should use

doctest:...: UserWarning

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

[videlec]

comment:12

A doctest still fails.

[videlec]

Work Issues: failing doctest

[videlec]

Changed work issues from failing doctest to none

[videlec]

comment:55

Thanks.

There are changes that affect two of William's books. I sent him an e-mail (cc'ed in sage-devel): see this thread.

Vincent

[fchapoton]

Changed work issues from doctest continuation to none

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

ec4a4ba

trac #14567: fix doctest

[sagetrac-git]

Changed commit from 925deeb to ec4a4ba

[videlec]

comment:59

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 sage-devel thread since a month now.

Vincent

[rwst]

comment:60

Replying to @videlec:

the one line you add to the file was wrong. I just replace it.

Oh well, thanks.

[videlec]

comment:61

Note: merge cleanly on sage-6.5.beta6 and tests pass in sage/rings, sage/modular and sage/tests!

[vbraun]

Changed branch from public/ticket/14567 to ec4a4ba

[williamstein]

comment:63

Hey, I just hit an annoying case...

sage: continued_fraction_list(1.575709393346379)
Error in lines 1-1
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...

[williamstein]

Changed commit from ec4a4ba to none

[videlec]

comment:64

Indeed... did you open a ticket?

[williamstein]

comment:65

Replying to @videlec:

Indeed... did you open a ticket?

No, can you?

[kcrisman]

comment:66

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.

[videlec]

comment:67

Replying to @kcrisman:

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.

Was continued fractions of real literals. Solved in #18901. I apologize to have not mentioned it here.

[jdemeyer]

comment:68

See #20012 for really deprecating CFF (ContinuedFractionField).