### Calculating the nearest square continued fraction of a quadratic irrational

This program finds the nearest square continued fraction expansion of a quadratic irrational α = (u + t√d)/v, where d,t,u,v are integers, d >1, and nonsquare, t and v nonzero.

We first convert α to (P+√d)/Q, where Q divides d - P^{2}.

Our algorithm is based on papers by A.A. Krisnaswami Ayyangar who defined a reduced surd on page 27 as "the successor of the successor of a special surd".

We use a more direct equivalent version which allows us to detect an NSCF-reduced complete quotient directly.

Let (P + √d)/Q = ξ_{0} be a *standard surd* (ie., Q divides d - P^{2}) and gcd(P, Q, (d-P^{2})/Q)=1). Let *a* be the integer part of ξ_{0}. Then we can write
ξ_{0} = a + Q'/(P + √d) or ξ_{0} = a + 1- Q"/(P" + √d),

where (P' + √d)/Q' and (P" + √d)/Q" are also standard surds.

We choose a_{0} to be *a* or *a + 1*, according as (i) |Q'| < |Q"| or |Q'| > |Q"|, if |Q'| ≠ |Q"| ; or (ii) if |Q'| = |Q"|, according as Q < 0 or Q > 0.
(This differs slightly in case (ii) from *Solving the Pell equation*, page 407, H.C. Williams, Proc. Millennial Conference on Number Theory, A.K. Peters, 2002, pp. 397-435.)

(We see that |P'^{2} - d|/|P"^{2} - d|=|Q'|/|Q"|. Hence |Q'| is ≤ or > |Q"| according as |P'^{2} - d| is ≤ or > |P"^{2} - d|.

So choosing the lesser of |Q'| and |Q"| is equivalent to choosing the nearest of the two squares P'^{2} and P"^{2} to d.)

Then (P + √d)/Q = ξ_{0} = a_{0} + ε_{1}/ ξ_{1} and where |ε_{1}| = 1 and ξ_{1} = (P_{1} + √d)/ Q_{1} > 1.

We proceed similarly with ξ_{1} and so on. Then we get *complete quotients* ξ_{n}, where

ξ_{n} = a_{n} + ε_{n + 1}/ ξ_{n + 1} and
ξ_{0} = a_{0} + ε_{1}/a_{1} + ε_{2}/a_{2} + · · ·

We have identities
P_{n+1} + P_{n} = a_{n}Q_{n},

P_{n+1}^{2} + ε_{n+1}Q_{n}Q_{n+1} = d.

The convergents A_{n}/B_{n} are defined by
A_{-2} = 0,
A_{-1} = 1,
B_{-2} = 1,
B_{-1} = 0 and for k ≥ -1,
A_{k+1} = a_{k+1}A_{k} + ε_{k+1}A_{k-1},

B_{k+1} = a_{k+1}B_{k} + ε_{k+1}B_{k-1}.

We print the partial numerators (*Teilzähler* ) ε_{n}, the partial denominators (*Teilnenner* ) a_{n}, the convergents and complete quotients, with the period elements in bold font.

*Last modified 29th July 2010*

Return to main page