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 and 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.

The nearest integer continued fraction of Hurwitz and Minnegerode is closely related to the present one, which is described in Perron's Band 1, page 143. This is spelled out in a paper of the author.

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

Last modified 21st July 2015
Return to main page