An algorithm for converting the regular continued fraction period to the nearest integer continued fraction

An algorithm for converting the regular continued fraction (RCF) period to the nearest integer continued fraction (NICF)

A similar algorithm was presented by Selenius for converting the RCF of ξ0=√D to NSCF, but is valid if ξ0=(P0+√D)/Q0 is reduced or ξ0=(P0+√D)/Q0 is not reduced, but Q0>0.

See Clas-Olaf Selenius, Konstruction und Theorie Halbregelmässiger Kettenbrüche mit idealer relativer Approximation, Acta Acad. Abo. Math. Phys. 22, (1960), 64-66.

Here ξ0=(u+t√d)/v, t non-zero, u,v,t,d integers, d > 1 and non-square.

We find the NICF expansion until the end of the first RCF period is reached.
For quadratic surds such as √D, we get the NICF expansion as far as the end of the first period. However this is not in general the case. (See paper.) The output includes the positive and negative representations of the resulting NICF complete quotients &xin

(Pn,Qn) = an + (P'n,Q'n)-1 = an + 1 - (P"n,Q"n)-1,

where (Pn,Qn) represents ξn = (Pn + √d)/Qn and an = ⌊&xin⌋.

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

Last modified 28nd April 2008
Return to main page