Calculating the nearest integer continued fraction of a quadratic irrational

This program finds the half-regular (halbregelmäßiger) nearest integer (nächsten Ganzen) 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 (u+√d) / v, where v divides d - u2.
Our account is based on Solving the Pell equation, H.C. Williams, Proc. Millennial Conference on Number Theory, A.K. Peters, 2002, pp. 405-406.

Let [θ] denote the nearest integer to θ. i.e. [θ] = ⌊θ + 1/2⌋.
Define a sequence of complete convergents by x0 = (u+√d) / v, xn = bn + an+1 / xn+1, where bn = [xn], n ≥ 0; also an = ±1, where sign(an+1) = sign(xn - bn).
This gives a continued fraction x0 = b0 + a1 / b1+ ···, where bi ≥ 2 for all i ≥ 1 and ai = ±1.

Write xk = (Pk + √d) / Qk, so that P0 = u and Q0 = v. Then

bk = [(Pk + √d) / Qk],
Pk+1 = bkQk - Pk,
Qk+1 = ak+1(d - P2k+1) / Qk > 0.

(We use a nearest-integer formula for [x/m], m a non-zero integer.)

We then find the least k ≥ 1 such that Pn+k = Pn and Qn+k = Qn and this leads to a period of length k.

The convergents An / Bn are defined by A-2 = 0, A-1 = 1, B-2 = 1, B-1 = 0 and for k ≥ -1,

Ak+1 = bk+1Ak + ak+1Ak-1
Bk+1 = bk+1Bk + ak+1Bk-1.

E=1 prints the partial numerators (Teilzählern) an, partial denominators (Teilnennern) bn, convergents and complete quotients, whereas E=0 prints only the partial quotients.
We use a definition of reduced complete quotient proposed by John Robertson:

If xn = (Pn + √d)/Qn and yn = (Pn - √d)/Qn and r = (3 - √5)/2, then

xn > 2 and -1 + r < yn < r or
xn = 3 - r = (3 + √5)/2.

(This is done by a function-call in which the scale is set to 10. There is hence a small chance that a false value may be returned, so the program is exited if the number of partial quotients reaches 5000. )

We then find the least k ≥ 1 such that Pn+k = Pn and Qn+k = Qn and this leads to a period of length k.

The period is printed in bold font.

(11th January 2008. It is not hard to prove that a reduced NICF complete quotient gives a purely periodic NICF and conversely.

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

Last modified 12th January 2008
Return to main page