### Calculating the optimal continued fraction of a quadratic irrational

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

We find the first occurrence of equality of complete quotients ξ_{j}=ξ_{j+k}, j < k. We know that if s_{j} > |Q_{0}|, this gives either a period or half-period. We then look for an inequality ξ_{j+t} ≠ ξ_{j+k+t}, 1 ≤ t < k. If no such inequality is detected, the OCF period length = l = 2 x NSCF period length = 2k; otherwise the OCF period length = l = NSCF period length = k.

We then progressively work back, checking to see if
a_{j-1}=a_{j+l-1} and
ε_{j}=ε_{j+l}
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.
Here a_{k}=[ξ_{k}] or a_{k}=[ξ_{k}]+1 and 0< v_{k}/(2v_{k}+s_{k}) <1/2.

e=1 prints the b_{k} and u_{k}/v_{k}.

Warning. The algorithm can get slowed down by the way I calculate a_{k}=[ξ_{k}+v_{k}/(2v_{k}+s_{k})]. e.g. ξ_{0}=(943+√57)/1681, which has period-length 2730. The author has written a faster BC OCF algorithm based on the NSCF algorithm.

*Last modified 12th November 2009*

Return to main page