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+ ···+ &epsilonj/aj+ &epsilonj+1/aj+1+ ···+ &epsilonj+l-1/aj+k-1+ &epsilonj+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 preprint in preparation of the author, titled Some connections between the optimal and nearest square continued fractions.
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.

Enter d (1 < d < 1015 and not a square):
Enter t (nonzero):
Enter u:
Enter v:

Last modified 3rd February 2010
Return to main page