### 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_{0}+
ε_{1}/a_{1}+
ε_{2}/a_{2}+ ···+
ε_{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_{0} + √d)/Q_{0} where Q_{0} divides d – P_{0}^{2}.

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_{0}|. 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^{2}+q^{2})/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