Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm doing continued fractions arithmetic. Is there a method to detect when a continued fractions period terminates?
Let me give you an example: $\sqrt{2} = [1; \overline{2}]$, $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ and $\sqrt{14} = [3; \overline{1, 2, 1, 6}]$.
Now clearly $\sqrt{2} \times \sqrt{7} = \sqrt{14}$, but if we do continued fractions arithmetic we get: $[1; \overline{2}] \times [2; \overline{1, 1, 1, 4}] = 3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, \dots$. Obviously this sequence never ends, since the continued fraction can always input a term from either $\sqrt{2}$ or $\sqrt{7}$ (as they are infinite).

So my question is: is there a mathematical method to detect when the period ends (during addition, subtraction, multiplication and division), rather than guessing and checking?
Maybe using the $z$ object (this "thing")? For example, after it emits the first $1$ it is: $\left \langle \begin{matrix}13 & 31 & 28 & 67\\ 11 & 27 2& 8 & 20 \end{matrix}\right \rangle$

and when the period starts again: $\left \langle \begin{matrix} 549 & 1317 & 2226 & 5335\\ 95 & 239 & 814 & 2010 \end{matrix} \right \rangle$
and again: $\left \langle \begin{matrix} 92029 & 222405 & 122610 & 296283\\ 41317 & 99487 & 37841 & 91039 \end{matrix} \right \rangle$.

Is there some kind of a pattern? I've noted none.

Thank you,
rubik

share|improve this question
    
You may find useful facts and references in the wikipedia article: en.wikipedia.org/wiki/Continued_fraction –  Beni Bogosel Dec 11 '11 at 10:42
    
@BeniBogosel: I read it, but it does not explain continued fraction arithmetic... –  rubik Dec 11 '11 at 10:46
    
I presume you've looked into the Floyd and Brent cycle detection algorithms? –  J. M. Dec 11 '11 at 10:46
    
@J.M.: Actually, it's what I wanted to avoid. I hoped there was some algorithm related to continued fractions, but if there are none, I think that's the way. –  rubik Dec 11 '11 at 10:51
    
Hi! I wrote those slides that you linked to. I'm a little surprised that the entries in the $z$ matrix didn't repeat; the original Gosper monograph treats a couple of similar problems where it does repeat. Is it possible that your code is not egesting terms frequently enough? But as I won't be able to take a close look at your example until later today, I suggest you have a look over the Gosper monograph and see if he has anything to say about your problem. –  MJD Jul 27 '12 at 15:22
add comment

4 Answers 4

This is more for J.M... it is not necessary to use cycle-detection algorithms if you stick with reduced quadratic forms, http://www.numbertheory.org/php/reduce.html for one description.

As I wrote in http://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014 if you are looking at only reduced forms $$ \langle a,b,c \rangle \approx a x^2 + b x y + c y^2, $$ with discriminant $\Delta = b^2 - 4 a c$ positive but not a square, with $$ 0 < b < \sqrt \Delta $$ and $$ \sqrt \Delta - b < 2 |a| < \sqrt \Delta + b. $$ Then, at any given step, find $\delta$ such that $$ \delta c > 0 $$ and $$ |\delta| = \left\lfloor \left| \frac{b +\sqrt \Delta}{2 c} \right|\right\rfloor $$ Now, the right adjacent form, or right neighbor, is given by $$ \langle a,b,c \rangle \rightarrow \langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle. $$ Lather, rinse, repeat.

If you begin with a reduced form $\langle a_0,b_0,c_0 \rangle$ then, after a finite number of steps, call it $n$ steps, we get an exact match of all three coefficients, $$\langle a_n,b_n,c_n \rangle = \langle a_0,b_0,c_0 \rangle$$

An indefinite binary quadratic form, with integer coefficients, corresponds to one of two quadratic irrationals given by the quadratic formula, where we are solving for either $x/y$ or $y/x$ according to taste. As the discriminant is positive and not a square, the roots are real numbers. It turns out that the number defined by the continued fraction (take the absolute values of the $\delta$'s) is not just positive but is larger than 1. Just one of those things.

I noticed in your code for $\sqrt N$ you had it terminate when the first coefficient returned to $\pm 1.$ Thts is not going to work if the reduced form you start with is $\langle 7,3,-7 \rangle$ where the exact method I describe is giving the continued fraction for $$ \frac{3 + \sqrt{205}}{14} $$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
7  3  -7

0  form   7 3 -7   delta  -1
1  form   -7 11 3   delta  4
2  form   3 13 -3   delta  -4
3  form   -3 11 7   delta  1
4  form   7 3 -7
minimum was   3rep -1 -1 disc   205 dSqrt 14.317821063  M_Ratio  4.183673
Automorph, written on right of Gram matrix:  
17  21
21  26
 Trace:  43   gcd(a21, a22 - a11, a12) : 3
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

To repeat, reduced indefinite integral quadratic form correspond to quadratic irrationals with purely periodic continued fractions. The cycle is complete if and only if the initial reduced form has been repeated. No other cycle detection is required.

The one caution is that, because we are taking the absolute values of the $\delta$'s, it is possible for the continued fraction period to be exactly half the period of the quadratic form. For example,

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
61

0  form   1 14 -12   delta  -1
1  form   -12 10 3   delta  4
2  form   3 14 -4   delta  -3
3  form   -4 10 9   delta  1
4  form   9 8 -5   delta  -2
5  form   -5 12 5   delta  2
6  form   5 8 -9   delta  -1
7  form   -9 10 4   delta  3
8  form   4 14 -3   delta  -4
9  form   -3 10 12   delta  1
10  form   12 14 -1   delta  -14
11  form   -1 14 12   delta  1
12  form   12 10 -3   delta  -4
13  form   -3 14 4   delta  3
14  form   4 10 -9   delta  -1
15  form   -9 8 5   delta  2
16  form   5 12 -5   delta  -2
17  form   -5 8 9   delta  1
18  form   9 10 -4   delta  -3
19  form   -4 14 3   delta  4
20  form   3 10 -12   delta  -1
21  form   -12 14 1   delta  14
22  form   1 14 -12

 disc   244
Automorph, written on right of Gram matrix:  
-183241189  1581119536
-226153980  945570387


 Pell automorph 
-1766319049  -910490892
-226153980  -1766319049

Pell unit 
1766319049^2 - 61 * 226153980^2 = 1 

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

The above is giving the continued fraction for $$ \frac{7 + \sqrt{61}}{12},$$ So I think we are always getting the largest value of $x/y$ rather than $y/x.$ For your purpose, this is just right, you are putting a 7 in front, which uses the reciprocal of the above, to get $$ 7 + \; \; \frac{12}{ \sqrt{61} + 7} $$ which works out to $\sqrt 61$ when you rationalize the denominator.

Please, read chapter 3, pages 21-48, in Binary Quadratic Forms by Duncan A. Buell, AMAZON

share|improve this answer
    
Interesting... :) –  J. M. Dec 11 '11 at 22:07
    
Hi, J.M. Yes, there is very little to it. There is no need for high decimal precision, and no need for cycle detection. It is necessary, exactly once, to correctly find $\lfloor \sqrt \Delta \rfloor,$ which can be done with integer arithmetic, and simply saved under another variable name. At each step, finding the new $\delta$ is also integer arithmetic. Just in case, I wrote my own square root finder in integers using Newton's method on integers until consecutive estimates are within 5 of each other, then I just take the final one and loop it up or down by 1's as needed. –  Will Jagy Dec 11 '11 at 22:25
    
Sorry for the delay, thank you for your reply! –  rubik Dec 15 '11 at 15:25
    
I stop the loop when $a = \pm 1$ because I am generating the continued fraction from a square root (and $a$ is always $1$ in the beginning), not from a generic binary quadratic form. Just out for curiosity, how do you calculate the initial coefficients from a binary quadratic form $\displaystyle\frac{a + \sqrt{b}}{c}$? I looked at the book you linked but for now I cannot buy it. Thank you –  rubik Dec 15 '11 at 15:29
    
@rubik , I get $c^2 x^2 - 2 a c x y + ( a^2 - b) y^2$ using your letters, in your case $\Delta = 4 a^2 b.$ This is probably not "reduced." In Buell's book, Proposition 3.3, proof pages 22-23, a finite number of steps in the exact procedure I illustrate takes any form to a reduced one, and a simple multiplication of 2 by 2 matrices at each step results in a 2 by 2 matrix that tells you how you got there. Many books discuss this. $\langle 1, 0, -n \rangle$ is never reduced, but we construct the equivalent $\langle 1, 2 \beta, \beta^2 -n \rangle,$ with $\beta = \lfloor \sqrt n \rfloor.$ –  Will Jagy Dec 15 '11 at 22:07
show 4 more comments

In the case of $\sqrt n$, it is extremely easy to tell when you've reached the end of the period; it's when you get a partial quotient twice the integer part. Look at your examples for $n=2,7,14$; the integer parts are $1,2,3$, respectively, and the periods end with $2,4,6$, respectively.

But if you don't know you're working with $\sqrt n$; if, say, you have the continued fractions for $\sqrt2/\pi$ and $\pi$, but you don't know it, I don't see how you'll ever know for sure that the product is periodic. But surely the same question arises if you have the decimal expansions of $\pi$ and $1/\pi$ and you don't know it; how can you ever know for sure that the product is $1$?

share|improve this answer
    
Or for that matter, if you begin with the continued fractions for $\sqrt{14}$ and $1/\sqrt{14}$ and multiply ... what happens then? –  Greg Martin Dec 11 '11 at 21:45
    
Unfortunately I am doing continued fractions arithmetic so I only have two simple CFs and I don't know where they come from... –  rubik Dec 15 '11 at 15:31
    
@GregMartin: Actually when multiplying $\sqrt{14}$ and $1/\sqrt{14}$ it loops forever without emitting a value. But I don't think this is a problem, since I can add a check before starting the computation (as the reciprocal of a continued fraction $[a_0; a_1, \dots a_n]$ is $[0; a_0, a_1, \dots, a_n]$ and vice-versa). –  rubik Dec 15 '11 at 15:35
add comment

A continuous fraction ends its period when $a_i = 2 * a_0$ example : $\sqrt{23} = [4;1,3,1,8]$ => $8 = 2* 4$

Or am I misunderstanding the question ?

share|improve this answer
    
That's what Gerry Myerson answered but it only applies to square roots, sorry ! –  hoang Jul 27 '12 at 11:57
add comment

It may sound a bit trivial, but actually, the important qustion would be: When has a fraction a period, i.e., when is there repetitive bahvior in the digits. It is known that irrational numbers are non-terminating, non-periodic decimal fractions. Using simple set-theory, i.e., taking the complement of the set of irrational numbers in the set of real numbers, we find, that either the rational numbers are terminating decimal fractions or periodic fractions. In either case, by the construction of the rational numbers, it is possible to find an expression like this: $q=\dfrac{n}{m}, n\in\mathbb{Z}, m\in\mathbb{N}$. Note that this expression needn't be unique!. Hence, after having added $m$ times the number $q$ we're done. So far about the theory. My experience has told me that these questions are the practical ones, i.e., those of little mathematical interest (b.t.w.: I am a pure mathematician working in global analysis, differntial topology and differential geometry <---- Purest mathematics apart from logic). I think that numerically one could find the answer to your problem, but in general, you will have to stick to guessing and checking. But perhaps when you learn abstract algebra and number theory combined with logic, you come across some solution (I have heard abstract algebra in the shortened version for geometers :D)

share|improve this answer
    
Thank you for your quick reply. I find a bit difficult following your reasoning, can you give me just an example? Actually, I know when a fraction has a period: when one of the input has it. –  rubik Dec 11 '11 at 10:37
5  
I don't see how this answer addresses the question at all. –  Greg Martin Dec 11 '11 at 21:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.