Calculating the optimal continued fraction of a quadratic irrational using the nearest square continued fraction method

This program finds the optimal continued fraction expansion as far as the end of the first period of a quadratic irrational x = (u + t√d)/v, where d,t,u,v are integers, d >1 and nonsquare, t and v nonzero:

x=a₀+ ε₁/a₁+ ε₂/a₂+ ···+ ε_j/a_j+ ε_j+1/a_j+1+ ···+ ε_j+l-1/a_j+k-1+ ε_j+l/···

where the first least period is printed in boldface. We first convert x to (P₀ + √d)/Q₀ where Q₀ divides d – P₀².
The algorithm is based on the paper Optimal continued fractions by Wieb Bosma, Indag. Math. 49 (1987) 353-379 (see pseudo-code) and a forthcoming paper of the author.
We first find an OCF complete quotient which is NSCF reduced and for which s_k > |Q₀|. This will be the start of an OCF period of length p = k' or 2k', where k' is the NSCF period length. At this point we switch to using the NSCF algorithm, with at most two perturbations in an NSCF period, which are dealt using formulae derived from an analysis of the case when the NSCF period contains a surd of the form (p+q+√p²+q²)/p, p > 2q > 0.
We then progressively work back, checking to see if a_j-1=a_j+p-1 and ε_j=ε_j+p etc. to get the first least period.

We output the partial numerators and denominators ε_k and a_k, the complete quotients ξ_k=(P_k + √d)/Q_k and the convergents r_k/s_k, with the first least period highlighted in boldface.
E = 1 prints everything, while E = 0 only prints the continued fraction up to the end of the first period.

Last modified 27th October 2011
Return to main page