Calculating the backward continued fraction of a quadratic irrational

This program finds the backward 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.
With ξ0 = α, for i ≥ 0, ai = int(ζi) + 1 and ζi+1 = 1/(ai - ζi), we get a finite continued fraction which eventually becomes periodic

where ai ≥ 2 for i ≥ 1.

Here a quadratic surd α is reduced if α > 1 > α' > 0 and these are the surds which have a purely periodic continued fraction expansion. See implementation as a BC program.

This continued fraction is mentioned in F. Hirzebruch's paper Hilbert modular surfaces, L'Enseignement Math. 19 (1973) and a paper by Don Zagier, A Kronecker Limit Formula for Real Quadratic fields, Math. Ann, 213, 153-184 (1975) especially pages 177-183. Also see Zetafunktionen und quadratische Körper, Eine Einführung in die höhere Zahlentheorie, Don Zagier, Springer 1981.
Hirzebruch on page 241 proved that if p=4n+3 is a prime and h(p) = 1, then h(-p) = (a1 + ··· + ar)/3 - r, where r is the period length of the least integer continued fraction of √p.

Here h(p) is the class number of the real quadratic field ℚ(√p) and h(-p) is the class number of the imaginary quadratic field ℚ(√-p).

Hirzebruch also noted that h(-p) = (-b1+b2 - ··· + b2s)/3, where the bi are partial quotients of the simple continued fraction expansion of √p and 2s is the period length.

The convergents Ai/Bi are calculated as follows:
A-1 = 1, B-1 = 0, A0 = a0, B0 = 1,
Ai = aiAi-1 - Ai-2, Bi = aiBi-1 - Bi-2, i ≥ 1.

We first convert α to (P + √d)/Q, where Q divides d - P2 and gcd(P, Q, (d - P2)/Q) = 1.
We print the partial quotients an, the convergents Ai/Bi and complete quotients ζi with the period partial quotients in bold font.

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

Last modified 23rd November 2011
Return to main page