Calculating the nearest square continued fraction of a quadratic irrational

This program finds the nearest square 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 (P+√d)/Q, where Q divides d - P².
Our account is based on papers by A.A. Krisnaswami Ayyangar whose definition of reduced surd on page 27 as "the successor of the successor of a special surd". This definition makes our period usually start one partial quotient later than it should.
Let (P + √d)/Q = ξ₀ be a standard surd (ie. Q divides d - P²) and a the integer part of ξ₀. Then we can write

ξ₀ = a + Q'/(P + √d) (I) or ξ₀ = a + 1- Q"/(P" + √d) (II)

where (P' + √d)/Q' and (P" + √d)/Q" are also standard surds.
We choose b₀ to be a or a + 1, according as (i) |Q'| < |Q"| or |Q'| > |Q"|, if |Q'| ≠ |Q"| ; or (ii) if |Q'| = |Q"|, according as Q < 0 or Q > 0.

(This differs slightly in case (ii) from Solving the Pell equation, page 407, H.C. Williams, Proc. Millennial Conference on Number Theory, A.K. Peters, 2002, pp. 397-435.)

(We see that |P'² - d|/|P"² - d|=|Q'|/|Q"|. Hence |Q'| is ≤ or > |Q"| according as |P'² - d| is ≤ or > |P"² - d|.
So choosing the lesser of |Q'| and |Q"| is equivalent to choosing the nearest of the two squares P'² and P"² to d.)

Then (P + √d)/Q = ξ₀ = b₀ + a₁/ξ₁ and where |a₁| = 1 and ξ₁ = (P₁ + √d)/Q₁ > 1.

We proceed similarly with ξ₁ and so on. Then we get complete quotients ξ_n, where

ξ_n = b_n + a_{n + 1}/ξ_{n + 1} and ξ₀ = b₀ + a₁/b₁ + a₂/b₂ + · · ·

We have identities

P_n+1 + P_n = b_nQ_n and P_n+1² + a_n+1Q_nQ_n+1 = d.

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+1A_k + a_k+1A_k-1
B_k+1 = b_k+1B_k + a_k+1B_k-1.

E=1 prints the partial numerators (Teilzähler ) a_n, the partial denominators (Teilnenner ) b_n, the convergents and complete quotients, whereas E=0 prints only the partial numerators and denominators.
The period is printed in bold font.

Last modified 18th Aoril 2008
Return to main page