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 – u2.
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 x0 = (u + √d)/v, xn = an – 1/xn+1, where an = [xn], n ≥ 0.
This gives a continued fraction x0 = a0 – 1/a1– ···, where |ai| ≥ 2 for all i ≥ 1.
The notation x0 = (a0,a1,...) goes back to A. Hurwitz, Werke, Band II, Seite 85.

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

qk = [(Pk + √d)/Qk],
Pk+1 = qkQk – Pk,
Qk+1 = (P2k+1 – d)/ Qk.

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

The first Hurwitz-reduced complete quotient xn = (Pn + √d)/Qn (see Werke, Band II, Seite 102) is located. ie.
with yn = (Pn – √d)/Qn and r = (3 – √5)/2,

xn > 2 and -1 + r < yn < r or
xn < -2 and -r < yn < 1 – r or
xn = 3 – r = (3 + √5)/2, 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 convergents An/Bn are defined by A-2 = 0, A-1 = 1, B-2 = -1, B-1 = 0 and for k ≥ -1,

Ak+1 = qk+1Ak – Ak-1
Bk+1 = qk+1Bk – Bk-1.

E=1 prints the partial quotients an, 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.

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