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=a0+ ε1/a1+ ε2/a2+ ···+ εj/aj+ εj+1/aj+1+ ···+ εj+l-1/aj+k-1+ εj+l/···

where the first least period is printed in boldface. We first convert x to (P0 + √d)/Q0 where Q0 divides d – P02.
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 sk > |Q0|. 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+√p2+q2)/p, p > 2q > 0.
We then progressively work back, checking to see if aj-1=aj+p-1 and εjj+p etc. to get the first least period.

We output the partial numerators and denominators εk and ak, the complete quotients ξk=(Pk + √d)/Qk and the convergents rk/sk, 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.

Enter d (1 < d < 1010 and not a square):
Enter t (nonzero):
Enter u:
Enter v:
Enter E (0 or 1):

Last modified 27th October 2011
Return to main page