continued fraction of $3 + 17\sqrt{3} $

Question

On a computer, I tried to iterate the Euclidean algorithm on the number $3 + 17\sqrt{3}$ and here is what I got:

\begin{array}{ccccrcrcrcr} 3 + 17\sqrt{3} &=& 32 &\cdot\;(& 1&+&0\sqrt{3} &)+(& -29 &+& 17\sqrt{3}) \\ 1 &=& 13 &\cdot\;(& -29 &+& 17 \sqrt{3}) &)+(& 59 &-& 34\sqrt{3})\\ &\vdots& \end{array}

Reading off the quotients, I got the continued fraction digit $3 + 17\sqrt{3} = [32, \overline{2,4,29,4,2,58}]$.

---

My successive remainders get smaller and smaller while the real and $\sqrt{d}$ parts get larger and larger. For example:

$$ -29 + 17 \sqrt{3} = 0.444\dots$$

In order to be exact, I used integers. I noticed my numbers are of the form $a + b \sqrt{d}$ where $a, b \gg 1$ are getting quite large.

$$70226 -40545\sqrt{3} = 7.11 \times 10^{-6}$$

Sometimes, when I run this algorithm, my computer crashes because the numbers get so large. How alter my Euclidean algorithm to avoid this?

Answer 1

Note: I give a description of the algorithm used below at http://math.blogoverflow.com/2014/08/23/binary-quadratic-forms-over-the-rational-integers-and-class-numbers-of-quadratic-%EF%AC%81elds/

I'm not so clear what you want here. I can say, though, that finding the continued fraction for a "quadratic irrational" has a method, due to Lagrange and Gauss, that requires no decimal accuracy whatsoever. Your number satisfies $$ \lambda^2 - 6 \lambda - 858 = 0, $$ so I put in the indefinite quadratic form $$ x^2 - 6 xy - 858 y^2 $$ and asked for the cycle of reduced forms. Note that the cyclic part uses only "reduced" quadratic forms $a x^2 + bxy+cy^2.$ The traditional definition of reduced is equivalent to: $$ \color{blue}{ ac < 0 \; \; \; \; \mbox{AND} \; \; \; \; b > |a+c| } $$ As you see below, any indefinite for, discriminant not a square, can be carried into a reduced form by a finite numbers of steps, exactly the same steps that carry us through the cycle of reduced forms equivalent (under $SL_2 \mathbb Z$ action) to the original. Buell, page 22, Proposition 3.3.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus ./indefCycle 1 -6 -858

  0  form              1          -6        -858  delta      0
  1  form           -858           6           1  delta     32
  2  form              1          58         -26


          -1         -32
           0          -1

To Return  
          -1          32
           0          -1

0  form   1 58 -26   delta  -2     ambiguous  
1  form   -26 46 13   delta  4
2  form   13 58 -2   delta  -29
3  form   -2 58 13   delta  4     ambiguous  
4  form   13 46 -26   delta  -2
5  form   -26 58 1   delta  58
6  form   1 58 -26


  form   1 x^2  + 58 x y  -26 y^2 

minimum was   1rep   x = 1   y = 0 disc   3468 dSqrt 58.889727457  M_Ratio  3468
Automorph, written on right of Gram matrix:  
-1061  -62010
-2385  -139391
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus

Note that the absolute values of my numbers called "delta" are your continued fraction coefficients.

The source that has the whole algorithm is Duncan A. Buell, Binary Quadratic Forms (1989), indeed it is just a few pages that are critical. There is a little more in Leonard Eugene Dickson, Introduction to the Theory of Numbers (1929).