### 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 – u^{2}.

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 x_{0} = (u + √d) / v and x_{n} = b_{n} + a_{n+1} / x_{n+1}, where b_{n} = [x_{n}], n ≥ 0; also a_{n} = ±1, where sign(a_{n+1}) = sign(x_{n} – b_{n}). This gives a continued fraction x_{0} = b_{0} + a_{1} / b_{1}+ ···, where b_{i} ≥ 2 for all i ≥ 1 and a_{i} = ±1.

Write x_{k} = (P_{k} + √d) / Q_{k}, so that P_{0} = u and Q_{0} = v. Then

b_{k} = [(P_{k} + √d) / Q_{k}],

P_{k+1} = b_{k}Q_{k} – P_{k},

Q_{k+1} = a_{k+1}(d – P^{2}_{k+1}) / Q_{k} > 0.

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

We then find the least k ≥ 1 such that P_{n+k} = P_{n} and Q_{n+k} = Q_{n} and this leads to a period of length k.

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} = b_{k+1}A_{k} + a_{k+1}A_{k-1}

B_{k+1} = b_{k+1}B_{k} + a_{k+1}B_{k-1}.

E=1 prints the partial numerators (Teilzählern) a_{n}, partial denominators (Teilnennern) b_{n}, 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 x_{n} = (P_{n} + √d)/Q_{n} and
y_{n} = (P_{n} - √d)/Q_{n} and r = (3 – √5)/2, then

x_{n} > 2 and -1 + r < y_{n} < r or

x_{n} = 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 P_{n+k} = P_{n} and Q_{n+k} = Q_{n} 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.

*Last modified 21st July 2015*

Return to main page