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₀+ ε₁/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).
We find the first occurrence of equality of complete quotients ξ_j=ξ_j+k, j < k. We know that if s_j > |Q₀|, 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. ξ₀=(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