Revision history [back]

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

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

Algorithm for finding the period of a quadratic irrational

1. Input: $(a,b,c)\in Z \times N\times Z$ and $b$ not a perfect square. This triple represents $\frac{a+\sqrt{b}}{c}$.

2. 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')$

3. Set $P_{0}=a'$ , $Q_{0}= c'$, $d=c'$.

4. For $k\geq0$ set

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

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

(c) $P_{k+1}=a_{k}Q_{k}-P_{k}$

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

1. Then $\alpha_{0}=\frac{a+\sqrt{b}}{c}=[a_{0},a_{1},a_{2},...]$

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