Calculating the optimal continued fraction of a quadratic irrational

This program finds the first n terms of the optimal continued fraction expansion
x=a0+ ε1/a1+ ε2/a2+ ··· of a quadratic irrational x = (u+t√d)/v, where d,t,u,v are integers, d >1 and nonsquare, t and v nonzero.
We first convert x to (P0+√d)/Q0 where Q0 divides d - P02.
Our account is based on the paper Optimal continued fractions by Wieb Bosma, Indag. Math. 49 (1987) 353-379. (See pseudo-code.)

We output the partial numerators and denominators εk and ak, the complete quotients ξk=(Pk+√d)/Qk and the convergents Ak/Bk for k = 0,,,n.
e=1 prints the bk and uk/vk.

Enter d (1 < d < 1015 and not a square):
Enter t (nonzero):
Enter u:
Enter v:
Enter n: (> 0)
Enter e: (0 or 1)

Last modified 2nd April 2008
Return to main page