Revision history [back]

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

1. Check if $\zeta$ is purely periodic (using the theorem above).
2. 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.
3. If $\zeta$ isn’t 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$.