An analogue of the nearest integer continued fraction for certain cubic irrationalities
Authors:
H. C. Williams and G. W. Dueck
Journal:
Math. Comp. 42 (1984), 683705
MSC:
Primary 11J70; Secondary 11A55, 11Y65
MathSciNet review:
736461
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be any irrational and define to be that integer such that . Put , , , . Then the r's here are the partial quotients of the nearest integer continued fraction (NICF) expansion of . When D is a positive nonsquare integer, and , this expansion is periodic. It can be used to find the regulator of in less than 75 percent of the time needed by the usual continued fraction algorithm. A geometric interpretation of this algorithm is given and this is used to extend the NICF to a nearest integer analogue of the Voronoi Continued Fraction, which is used to find the regulator of a cubic field with negative discriminant . This new algorithm (NIVCF) is periodic and can be used to find the regulator of . If , the NIVCF algorithm can be used to find any algebraic integer of such that . Numerical results suggest that the NIVCF algorithm finds the regulator of in about 80 percent of the time needed by Voronoi's algorithm.
 [1]
William
W. Adams, On a relationship between the
convergents of the nearest integer and regular continued
fractions, Math. Comp. 33
(1979), no. 148, 1321–1331.
MR 537978
(82g:10078), http://dx.doi.org/10.1090/S00255718197905379789
 [2]
B.
N. Delone and D.
K. Faddeev, The theory of irrationalities of the third degree,
Translations of Mathematical Monographs, Vol. 10, American Mathematical
Society, Providence, R.I., 1964. MR 0160744
(28 #3955)
 [3]
A.
Hurwitz, Über eine besondere Art der KettenbruchEntwicklung
reeller Grössen, Acta Math. 12 (1889),
no. 1, 367–405 (German). MR
1554778, http://dx.doi.org/10.1007/BF02391885
 [4]
B. Minnigerode, "Über eine neue Methode, die Pellsche Gleichung aufzulösen," Gott. Nachr. 1873, 619653.
 [5]
G. Voronoi, On a Generalization of the Algorithm of Continued Fractions, Doctoral Dissertation, Warsaw, 1896. (Russian)
 [6]
H.
C. Williams and P.
A. Buhr, Calculation of the regulator of
𝑄(√𝐷) by use of the nearest integer continued
fraction algorithm, Math. Comp.
33 (1979), no. 145, 369–381. MR 514833
(80e:12003), http://dx.doi.org/10.1090/S00255718197905148331
 [7]
H.
C. Williams, Some results concerning the nearest integer continued
fraction expansion of √𝐷, J. Reine Angew. Math.
315 (1980), 1–15. MR 564520
(81f:10015), http://dx.doi.org/10.1515/crll.1980.315.1
 [8]
H.
C. Williams, G.
Cormack, and E.
Seah, Calculation of the regulator of a pure
cubic field, Math. Comp.
34 (1980), no. 150, 567–611. MR 559205
(81d:12003), http://dx.doi.org/10.1090/S00255718198005592057
 [9]
H.
C. Williams, Improving the speed of calculating the
regulator of certain pure cubic fields, Math.
Comp. 35 (1980), no. 152, 1423–1434. MR 583520
(82a:12003), http://dx.doi.org/10.1090/S00255718198005835204
 [10]
H.
C. Williams, G.
W. Dueck, and B.
K. Schmid, A rapid method of evaluating the
regulator and class number of a pure cubic field, Math. Comp. 41 (1983), no. 163, 235–286. MR 701638
(84m:12010), http://dx.doi.org/10.1090/S00255718198307016382
 [1]
 W. W. Adams, "On the relationship between the convergents of the nearest integer and regular continued fractions," Math. Comp., v. 33, 1979, pp. 13211331. MR 537978 (82g:10078)
 [2]
 B. N. Delone & D. K. Faddeev, The Theory of Irrationalities of the Third Degree, Transl. Math. Monos., vol. 10, Amer. Math. Soc., Providence, R. I., 1964. MR 0160744 (28:3955)
 [3]
 A. Hurwitz, "Über eine besondere Art der Kettenbruchentwicklung reeller Gröszen," Acta Math., v. 12, 1889, pp. 367405. MR 1554778
 [4]
 B. Minnigerode, "Über eine neue Methode, die Pellsche Gleichung aufzulösen," Gott. Nachr. 1873, 619653.
 [5]
 G. Voronoi, On a Generalization of the Algorithm of Continued Fractions, Doctoral Dissertation, Warsaw, 1896. (Russian)
 [6]
 H. C. Williams & P. Buhr, "Calculation of the regulator of by use of the nearest integer continued fraction algorithm," Math. Comp. v. 33, 1979, pp. 369381. MR 514833 (80e:12003)
 [7]
 H. C. Williams, "Some results concerning the nearest integer continued fraction expansion of ," J. Reine Angew. Math., v. 315, 1980, pp. 115. MR 564520 (81f:10015)
 [8]
 H. C. Williams, G. Cormack & E. Seah, "Calculation of the regulator of a pure cubic field," Math. Comp., v. 34, 1980, pp. 567611. MR 559205 (81d:12003)
 [9]
 H. C. Williams, "Improving the speed of calculating the regulator of certain pure cubic fields," Math. Comp., v. 34, 1980, pp. 14231434. MR 583520 (82a:12003)
 [10]
 H. C. Williams, G. W. Dueck & B. K. Schmid, "A rapid method of evaluating the regulator and class number of a pure cubic field," Math. Comp., v. 41, 1983, pp. 235286. MR 701638 (84m:12010)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11J70,
11A55,
11Y65
Retrieve articles in all journals
with MSC:
11J70,
11A55,
11Y65
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198407364617
PII:
S 00255718(1984)07364617
Article copyright:
© Copyright 1984
American Mathematical Society
