Refactor continued fractions

[vdelecroix]

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

[vdelecroix]

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

[vdelecroix]

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

[vdelecroix]

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

[chapoton]

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

[vdelecroix]

Replying to chapoton:

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.

[vdelecroix]

A doctest still fails.

[chapoton]

I have added a small clean-up patch (problems found with pyflakes):

• removed unused import
• removed unused variables
• corrected one wrong variable

[vdelecroix]

Replying to chapoton:

I have added a small clean-up 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!

[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 sage-5.9 and sage-5.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.

[vdelecroix]

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 sage-5.9 and sage-5.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 ?

[ppurka]

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.

[vdelecroix]

I uploaded a patch which applies on 5.12.rc0. I will now create a branch.

[ppurka]

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

[rws]

You have to use patch with the -l option, then it succeeds. I can open a git branch if this doesn't work for you.

[rws]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7e0af69

Trac #14567: reviewer's patch: enable docbuild

[rws]

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.

[tscrim]

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?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fb96ac7

Fix previous patch

[tmonteil]

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.

[tmonteil]

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 ?

[rws]

As to a unification, the coefficients could be viewed as a sequence generated by a rational ordinary generating function p(x)/q(x) (C-finite sequence, see #15714) where:

• q(x)=1 for rational contfracs (=finite sequence)
• q(x)=1-x^d with d the contfrac period for quad. irrationals (=infinite sequence)
• other p/q, e.g. (2+x+2x²-3x³-x⁴+x⁶)/(1-2x³+x⁶) for e. Of course, absent a theory these must be guessed but that code exists already.
• would make e+sqrt(2) exact

Arithmetic with p/q is obvious, only back-conversion to non-rational looks impossible at the moment to me.

[vdelecroix]

Tiny modifications

• merged in beta.5
• resolve some import in sage.rings.all

---

New commits:

​2120de5	Merge branch 'u/rws/ticket/14567' of trac.sagemath.org:sage into 14567-continued_fractions
​fba343b	fix import statements in sage.rings.all
​6a2d6aa	move farey to continued_fractions

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5bb8bd3	cont_frac: pn -> numberator, qn -> denominator
​8fbf106	update the code with respect to reviewer remarks

[vdelecroix]

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()
True

I 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 use RIF(x). Why not using x.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 replace pn() and qn() methods by numerator() and denominator() 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

[git]

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 14567-continued_fractions
​43de321	Merge branch 'u/vdelecroix/14567' of trac.sagemath.org:sage into 14567-continued_fractions

[vdelecroix]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b570179

trac 14567: continued fraction (based on 6.2.rc0)

[vdelecroix]

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

[rws]

For the record it is necessary to

sage -b
make doc-clean
make doc

to build the documentation. sage -docbuild will not suffice (fails).

[rws]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d59dbf5	trac #14567: update to sage 6.3.beta1
​da8a52b	trac #14567: fix code in words, plot and rational

[vdelecroix]

Thanks (a bug in plot and a bug in words).

Now the tests pass.

Vincent

[chapoton]

you need to use the new doc continuation style ...: (see patchbot report)

[chapoton]

new branch, where I have taken care of the doctests continuation. Bot should turn green.

---

New commits:

​7da398e	Merge branch 'u/vdelecroix/14567' of ssh://trac.sagemath.org:22/sage into 14567
​62fdcda	trac #14567 taking care of doctest continuation

[vdelecroix]

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 the-branch-I-need
git checkout -b a-good-name FETCH_HEAD

[kcrisman]

What remains to be done here to give positive review?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​925deeb

14567: reviewer's patch: add early example of continued_fraction_list

[rws]

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.

[vdelecroix]

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

[git]

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

​ec4a4ba

trac #14567: fix doctest

[vdelecroix]

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

[rws]

Replying to vdelecroix:

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

Oh well, thanks.

[vdelecroix]

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

[was]

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

[vdelecroix]

Indeed... did you open a ticket?

[was]

Replying to vdelecroix:

Indeed... did you open a ticket?

No, can you?

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

[vdelecroix]

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]

See #20012 for really deprecating CFF (ContinuedFractionField).