Processing math: 100%
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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 ζQ(D) be a positive quadratic irrational. Then ζ has a purely periodic continued fraction iff ζ>1 and the conjugate of ζ under the map DD is between -1 and 0.

Theorem(Lagrange?): The period of a purely periodic quadratic irrational ζ 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: ζ, a positive quadratic irrational in the form ζ=q+rD for rational numbers q,r.

  1. Check if ζ 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 ζ isn’t purely periodic, replace ζ with 1ζfloor(1ζ) 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.