Continued fraction expansion of quadratic irrationals

continued_fractions

asked 2011-05-16 02:49:17 +0200

Menny
69 ●3 ●5 ●8

updated 2011-05-16 09:44:26 +0200

Let me emphasize that I am very new to sage and to computing in general, but I did research as much as I could before asking this question.

It is well know that that quadratic irrationals has eventuallyperiodic continued fraction expansion. I really tried to find a function that gives me the period of a given quadratic irrational. The best I could find was in this forum: http://www.mail-archive.com/sage-supp...

It explains that you can get using GAP the PrePeriod+Period. It has two disadvantages: the first, you can't get the pure period, i.e., without the preperiod, and the second is that it is the input is not the number itself but the polynomial it solve. If this polynomial has many positive roots it is a problem...

I tried to look also in PARI and didn't find anything. I did see that it is written that sage itself does not have this function.

Let me also remark that such algorithm exist. My question: Is there a way (via packages that are contained in sage) to find the period of a given quadratic irrational?

Thanks a lot! Menny

edit retag flag offensive close merge delete

Comments

It seems that you are correct that this is not the case - yet. In fact, see http://groups.google.com/group/sage-support/tree/browse_frm/month/2008-05?_done=%2Fgroup%2Fsage-support%2Fbrowse_frm%2Fmonth%2F2008-05%3F& for something related. Can you point us to some of the algorithms? Also, the current expansion is in pure Python, so rather slow.

kcrisman ( 2011-05-16 12:27:01 +0200 )edit

I didn't find the algorithm yet, but you can see that it is implemented in maple: http://www.maplesoft.com/support/help/Maple/view.aspx?path=numtheory/cfrac I'll go hunting for the algorithms.

Menny ( 2011-05-16 15:48:22 +0200 )edit

It's also implemented (for some quadratic irrationals) in Mathematica / Wolfram|Alpha. See: http://www.wolframalpha.com/input/?i=continued+fraction+sqrt%2817%29%2F12 (period is 6) and http://www.wolframalpha.com/input/?i=continued+fraction+sqrt%28100027%29%2F12 (period is large, you'd have to count it yourself I guess after clicking "more terms" a bunch of times).

benjaminfjones ( 2011-05-16 20:16:07 +0200 )edit

I think what @Menny wanted was something that gives the period without having to count and click more terms :)

kcrisman ( 2011-05-17 09:57:18 +0200 )edit

I mainly want to be able to work with it through sage and manipulate the results I'm getting. I can seems to find the algorithms.... I looked in Cohen books, and asked for the help of google and didn't find anything yet. Is there a generic references of Number theory algorithms?

Menny ( 2011-05-17 11:02:18 +0200 )edit

add a comment

4 Answers

Sort by » oldest newest most voted

answered 2011-05-17 13:59:23 +0200

benjaminfjones
2775 ●8 ●44 ●76 http://bfj7.com/

As far as I can tell, there aren't any packages available in Sage beyond the GAP package you mention above. There is a relatively simple algorithm for finding the period and I think it would be worth implementing this in the continued fractions module in Sage.

I created a trac ticket for this enhancement: Trac #11345

A colleague of mine who works on diophantine approximation communicated an algorithm to me which I'll paraphrase below. The algorithm takes a specific quadratic irrational and would determine the pre-period (if desired), the periodic sequence, and the length of the period. The algorithm makes use of the following classical results (which I don't have specific references for yet).

Theorem(Galois): Let $\zeta\in\mathbb{Q}(\sqrt{D})$ be a positive quadratic irrational. Then $\zeta$ has a purely periodic continued fraction iff $\zeta > 1$ and the conjugate of $\zeta$ under the map $\sqrt{D}\mapsto -\sqrt{D}$ is between -1 and 0.

Theorem(Lagrange?): The period of a purely periodic quadratic irrational $\zeta$ as above has length at most $2D$ (and this upper bound is sharp?). I'll need to find a reference for that.

Algorithm: (to determine the period of a quadratic irrational number)

INPUT: $\zeta$, a positive quadratic irrational in the form $\zeta = q + r\sqrt{D}$ for rational numbers $q, r$.

Check if $\zeta$ is purely periodic (using the theorem above).
If so, we know that the period has length at most $2D$. We then determine the period by listing enough terms in the continued fraction approximation.
If $\zeta$ isnt purely periodic, replace $\zeta$ with $\frac{1}{\zeta}-\text{floor}(\frac{1}{\zeta})$ and go to step 1.

We get the length of the pre-period by counting the number of iterations above and we have an immediate upper bound on how much farther we have to search for the length of the period $2D$.

edit flag offensive delete link

Comments

I've already said this on the Trac ticket, but it might be worth seeing if there is any code from GAP we could use, at least as pseudo-code. Also, how would we check for this being a quadratic surd? Sometimes very complicated things (think Cardano's formula-type stuff) end up being surds upon clever manipulation.

kcrisman ( 2011-05-17 17:06:47 +0200 )edit

Just as a note, http://trac.sagemath.org/ticket/14567 seems to be almost ready...

kcrisman ( 2014-02-08 22:10:08 +0200 )edit

add a comment

answered 2011-05-17 18:28:34 +0200

Menny
69 ●3 ●5 ●8

As a continuation of the reply by Benjamin, Let me give some references and give more information.

Both Theorems appear in the book "Continued Fractions" By Andrew Mansfield Rockett and Peter Szüsz. The first is Theorem 3 on page 45, and the second is a remark before Theorem 1 on page 50. The second is not stated correctly (there should not be any coeffiecient before the square root):

Theorem(Lagrange Estimate): Let $t= \frac{P_0+\sqrt{D}}{Q_0}$ with $D$ not a perfect square and $P_0,Q_0$ are integers. Then the length of the period of $t$ is at most $2D$.

A better asymptotics is given by the following (which is Theorem 1 of page 50):

Theorem: Let $t$ be as above with the addtional assumption that $Q_0$ divide $D-P_0^2$. Then if $L(t)$ denoted the length of the period of $t$ then $$L(t)=O(\sqrt{D}log(D))$$

I'm not sure what the constant is (it is related to the divisor function)... I didn't read the proof yet!

edit flag offensive delete link

add a comment

answered 2011-07-13 00:05:38 +0200

Menny
69 ●3 ●5 ●8

Via the reference within this page: http://www.numbertheory.org/php/surd....

I found a more elegant algorithm than the one sketched above:

Algorithm for finding the period of a quadratic irrational

Input: $(a,b,c)\in Z \times N\times Z$ and $b$ not a perfect square. This triple represents $\frac{a+\sqrt{b}}{c}$.
If $c$ does not divide $b-a^{2}$ then multiply everything by $\frac{|c|}{|c|}$ , and get new triple that we call $(a',b',c')$
Set $P_{0}=a'$ , $Q_{0}= c'$, $d=c'$.
For $k\geq0$ set

(a) $\alpha_{k}=\frac{P_{k}+\sqrt{d}}{Q_{k}}$

(b) $a_{k}=\lfloor\alpha_{k}\rfloor$

(d) $Q_{k+1}=\frac{d-P_{k+1}^{2}}{Q_{k}}$

Then $\alpha_{0}=\frac{a+\sqrt{b}}{c}=[a_{0},a_{1},a_{2},...]$
Let $k< l$ be the first pair of integers which satisfy that $$(P_{k},Q_{k})=(P_{l},Q_{l})$$ then the period of $\alpha_{0}$ is $(a_{k},\dots,a_{l-1})$ .

Hopefully this will help implementing it...

edit flag offensive delete link

Comments

That's very helpful. Thanks for the reference. I had already implemented a first draft of the algorithm I described above, but I think what you've described here is going to be much faster. If you want to look at what I've got so far, email me.

benjaminfjones ( 2011-07-13 14:40:13 +0200 )edit

add a comment

answered 2014-02-08 06:40:06 +0200

rws
1139 ●2 ●19 ●44 http://google.com/+Ral...

updated 2014-02-20 02:50:05 +0200

The issue (among other things) is addressed in Sage by ticket 14567, after implementation of which you will be able to say:

sage: K.<sqrt11> = QuadraticField(11)
sage: cf = CFF(sqrt11); cf
[3; (3, 6)*]
sage: len(cf.period())
2

For literature, see also the OEIS database entry:

http://oeis.org/A003285

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Continued fraction expansion of quadratic irrationals

Comments

4 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Continued fraction expansion of quadratic irrationals edit

Comments

4 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Continued fraction expansion of quadratic irrationals