### Calculating the nearest integer continued fraction of Hurwitz for a quadratic irrational

This program finds the nearest integer 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 exercise 4, page 85 of *Quadratics*, R.A. Mollin, CRC Press 1995 and *Calculation of the Regulator of Q(√D) by Use of the Nearest Integer Continued Fraction Algorithm*, H.C. Williams and P.A. Buhr, Math. Comp. **33** (1979) 369-381 and *Mathematische Werke* Band II, A. Hurwitz, Seite 84-115.
Let [θ] denote the nearest integer to θ. i.e. [θ] = ⌊θ + 1/2⌋.

Define a sequence of *complete convergents* by x_{0} = (u + √d)/v, x_{n} = a_{n} – 1/x_{n+1}, where a_{n} = [x_{n}], n ≥ 0.

This gives a continued fraction x_{0} = a_{0} – 1/a_{1}– ···, where |a_{i}| ≥ 2 for all i ≥ 1.

The notation x_{0} = (a_{0},a_{1},...) goes back to A. Hurwitz, Werke, Band II, Seite 85.

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

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

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

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

(We use a nearest-integer formula for [x/m], m a non-zero integer.)
The first Hurwitz-reduced complete quotient x_{n} = (P_{n} + √d)/Q_{n} (see Werke, Band II, Seite 102) is located. ie.

with y_{n} = (P_{n} – √d)/Q_{n} and r = (3 – √5)/2,

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

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

x_{n} = 3 – r = (3 + √5)/2, 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 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} = q_{k+1}A_{k} – A_{k-1}

B_{k+1} = q_{k+1}B_{k} – B_{k-1}.

E=1 prints the partial quotients a_{n}, convergents and complete quotients, whereas E=0 prints only the partial quotients.

The period is printed in **bold** font.
The nearest integer continued fraction of Hurwitz and Minnegerode is closely related to the one in Perron's Band 1, page 143. This connection is spelled out in a paper of the author.

*Last modified 21st July 2015*

Return to main page